LOADING

加载过慢请开启缓存 浏览器默认开启

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site(2024武汉邀请赛)

题目Problem - B. Countless Me- Codeforces

分析:

假设最优的情况下,每个值为 $x_1$,$x_2$…$x_n$,则使给定序列变为最优值只需要一次,整个序列只需要n次,所以可以把序列变成任意序列。因为越$ | $越大,所以不难想到拆位并尽可能让高位置$0$。

我们不妨把所有值相加为$now$,从第$(1<<30)$ 开始高位往低位分析。设当前位为第$i$位,如果$now \le ((1<<i)-1)*n$ 那么可以当前位置0,否则我们尽量把当前位填更多$1$。(因为当前位置越多$1$,后面越容易置$0$,且因为当前位置$1$,拆成后面一定为偶数个$1$,在之后不能置$1$的情况下,一定会往前进位,那么现在置$1$不会更坏)

代码:

void solve(){
    int n,res=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        res+=x;
    }
    int ans=0;
    for(int i=30;i>=0;i--){
        int ver=((1ll<<i)-1)*n;
        if(res>ver)ans|=(1ll<<i),res-=min(n,res/(1ll<<i))*(1ll<<i);
    }
    cout<<ans<<"\n";
}