2021 CCPC Harbin I. power and zero (binary + thinking)

Problem - I - Codeforces

In view of ：I. Power and Zero( Binary system , thinking ）_Looy_cai The blog of -CSDN Blog

Ideas ：

Convert a string of decimal numbers into binary , Then add the digits , At this time, it may not be increasing from high to low , So we need to convert from high to low . Until from high to low, there is no decreasing state . At this time, the last one , That is, the one with the largest number , That's the answer. .

Be careful ：

When converting a string of numbers to binary , The binary length of each number may be different , So record the maximum length as the length of the binary array .

When switching from high to low , There is no guarantee that the state of non decreasing can be achieved by switching once , because bit[1] and bit[2] After the transformation ,bit[2] and bit[3] After conversion ,bit[2] It's getting smaller ,bit[1] And than bit[2] big , Therefore, it is necessary to keep cycling until the binary array reaches the state of no decrement from high to low .

Code ：

#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;
}