思路:思维

1.如果有奇数:直接合并是最少的，因为只要一次就能减少一个奇数，而除2操作至少需要1次才能消除一个偶数 2.如果没有奇数:先找到含最少2因子的数，把他除2得到奇数，然后按照情况1来做

python

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    lowest_div2 = 10**9 # 最小的除2次数
    even_num = 0 # 偶数个数
    for x in a:
        cnt = 0 # 获得x的除2次数
        while x % 2 == 0: # 除2
            x //= 2
            cnt += 1
        lowest_div2 = min(lowest_div2, cnt) # 更新最小的除2次数
        if cnt != 0:
            even_num += 1
    if even_num == n: # 全是偶数,需要先进行除2操作再合并
        ans = lowest_div2 + even_num - 1
    else: # 有奇数,直接合并
        ans = even_num
    print(ans)

Java

import java.util.*;

public class Main{
    public static int cal(List<Long> list){
        int ans =Integer.MAX_VALUE;
        for(long num:list){
            int cur=0;
            while(num%2==0){
                cur++;
                num/=2;
                if(cur>ans) break;
            }
            ans =Math.min(ans,cur);
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int T=Integer.parseInt(in.nextLine());
        while(T-->0){
            int n=Integer.parseInt(in.nextLine());
            List<Long> evenList =new ArrayList<>();
            //Collections.sort(evenList);
            int even=0,odd=0;
            String[] str=in.nextLine().split(" ");
            for(int i=0;i<n;i++){
                long a =Long.parseLong(str[i]);
                if(a%2==0){
                    even++;
                    evenList.add(a);
                }
                else odd++;
            }
            if(even==0) System.out.println(0);
            else if(odd>0) System.out.println(even);
            else{
                System.out.println(cal(evenList)+even-1);
            }
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>


using namespace std;



int main(){
    int T;
    cin>>T;

    while(T--){
        long long n;
        cin>>n;
        vector<long long> a(n);
        long long jco = 0;
        long long oco = 0;
        for(long long i=0;i<n;i++){
            cin>>a[i];
            if(a[i]%2!=0){
                jco++;
            }
            else{
                oco++;
            }
        }
        if(jco!=0){
            cout<<oco<<endl;
        }
        else{
            long long min2 = LONG_MAX;
            for(long long i=0;i<n;i++){
                long long s2 = 0;
                while (a[i]%2==0) {
                    s2++;
                    a[i]/=2;
                }
                min2 = min(s2,min2);
            }

            cout<<min2+oco-1<<endl;
        }
    }
}

题目内容

小红有一列正整数组成的数列，支持两种操作：

选取一个偶数，使其值减半

选取两个数字，移除并替换为两个数字的和

小红最终希望能够得到一个全为奇数的数列，请计算最少需要操作几次

输入描述

第一行一个数字$T$，代表测试用例组数$(0<T≤10)$

对于每个测试用例：

第一行为$n$，代表数组长度，$(0<n≤10^5)$

第二行$n$个正整数，$a_i,(0<a_i<10^{14})$

输出描述

对于每个测试用例，输出一个数字，代表最少需要操作次数

示例1

输入

3
3
2 4 4
2
1 9
5
1 2 3 4 5

输出

3
0
2

说明