2021 CCPC 哈尔滨 I. Power and Zero（二进制 + 思维）

Problem - I - Codeforces

借鉴于：I. Power and Zero(二进制，思维）_Looy_cai的博客-CSDN博客

思路：

将一串十进制的数转为二进制，然后各个数位相加，这时候从高到低可能不是递增的，所以要进行高位到低位的转换。直到从高到低都是不递减的状态。这时候最后一位，也就是数值最大的那一位，就是答案。

注意：

将一串数转为二进制时，每个数的二进制长度可能不同，所以要记录最大长度作为二进制数组的长度。

从高到低转换时，转换一遍是不能保证达到不递减的状态的，因为bit[1]和bit[2]转换后，bit[2]和bit[3]又转换后，bit[2]变小了，bit[1]又比bit[2]大了，所以要不断循环直到二进制数组达到从高到低都是不递减的状态。

代码：

#include<iostream>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int t, n;
int bit[50];

int main() {

    scanf("%d", &t);

    while(t --) {
        scanf("%d", &n);
        int x;
        int len = -1;
        memset(bit, 0, sizeof bit);
        for(int i = 0; i < n; i ++) {
            scanf("%d", &x);
            int ind = 0;
            while(x) {
                bit[++ ind] += x % 2;
                x /= 2;
            }
            len = max(len, ind);
        } 

        bool ok = true;
        while(ok) {
            ok = false;
            for(int i = len; i >= 2; i --) {
                if(bit[i] > bit[i - 1]) {
                    ok = true;
                    int avg = (bit[i] * 2 + bit[i - 1]) / 3;
                    bit[i - 1] += (bit[i] - avg) * 2;
                    bit[i] = avg;
                } 
            }
        }

        printf("%d\n", bit[1]);
    }    

    return 0;
}