贪心、数学、位运算

题目链接

考虑贪心，从高位向低位枚举，如果当前位必须为 $1$ 就把所有数的当前位尽量全部置为 $1$，这样可以最大化利用当前位，然后继续向低位枚举。

只需要维护所有数字的和，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
long long sum;
int n,ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        static int x;
        scanf("%d",&x);
        sum+=x;
    }
    for(int i=1<<30;i!=1;i>>=1) if(sum>=1ll*i*n-n+1){
        ans|=i;
        if(sum>=i*n) sum-=1ll*i*n;
        else sum%=i;
    }
    if(sum!=0) ans|=1;
    printf("%d\n",ans);
    return 0;
}