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