【CodeForces】CF1338A - Powered Addition【二进制】

题意

给出一个长度为$n(n<=100000)$的数组，在第$i$秒时可以任意选出一些数使它们的值增加$2^{i-1}$，问如果要使得该数组不递减至少需要多少秒？

思路

遍历数组，维护一个前缀最大值，如果当前$a[i]<ma{x}_{cur}$,说明当前$a[i]$需要补齐$ma{x}_{cur}-a[i]$大小，然后当前$a[i]$变为$ma{x}_{cur}$，最后$max(ma{x}_{cur}-a[i])$的二进制位数就是我们要求的答案。

AC代码

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

typedef long long ll;
typedef pair<int, int> p;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;

int a[maxn];
int h[maxn];

int main() {
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    while(t--){
    
        int n;
        cin >> n;
        int max_cur = INT32_MIN;
        int max_delta = INT32_MIN;
        for(int i = 1; i <= n; i++) cin >> a[i];
        for(int i = 1; i <= n; i++){
    
            if(a[i] > max_cur) max_cur = a[i];
            else max_delta = max(max_delta, max_cur-a[i]);
        }

        if(max_delta==INT32_MIN) cout<<0<<endl;
        else{
    
            int cnt = 0;
            while(max_delta) max_delta = max_delta >> 1, cnt++;
            cout<<cnt<<endl;
        }
    }
    return 0;
}