CF1869 D2. Candy Party (Easy&Hard Version) [二进制贪心]

传送门

先考虑$easy$版本,显然我们可以轻易得到每一个人最后的数字.那么我们每一个人又至少要给出一个数又要得到一个数的话,这两个数字的贡献就应该等于我们这个人的数字和平均数的差值.

不难发现二进制数其实有一个规律,就是一个数能被表示出$2^i?2^j$的话,那么这个数的二进制位上的一必须有且只有连续的一段.不然是无法被表示出来的.(证明暂略).并且如果这个数能被表示出来,$i$必然是最高位1的位置+1,$j$必然是最低位1的位置.

所以此时我们就得到了每一个数字的给出和得到,并且他们都是固定的.所以显然的,每一个给出应该和一个得到给定.所以我们只要记录一下给出和得到的个数然后判断一下就行了.

$Easy$版本到这里就解决了.

考虑$Hard$版本.此时我们的每一个人的操作改为了至多给一个人以及至多得到一个人.这和$Easy$版本有什么区别呢.不难发现当我们的差不为整二进制数(也就是可以表示为$2^k$)时,我们必然是需要一进一出的.所以此时和$Easy$没区别.区别在于整二进制数的时候,此时,$2^k$既能表示为$2^{k+1}?2^k$,又能直接给出/得到$2^k$,所以此时我们就比$Easy$多了一种选择.

那我们不妨直接将上述特殊的数字直接当做给出/得到$2^k$(并且把该数字记为可操作的数字).然后我们先这样暂时记录完所有给出和得到的数字之后.再从高位向低位逐位判断,如果数字不一样,就把上述可操作的数字改为两个数的差.这样贪心的填数.具体来说,如果给出的$2^k$多了,那我们就将可操作的得到的$2^{k?1}$改为得到$2^k$并且给出$2^{k?1}$

简单解释一下上述贪心策略的正确性(限于本人能力,无法给出严谨的数学证明).为了方便起见,不妨将数字为x时给出的总数记为$a[x]$,得到的记为$b[x]$.那此时他们大小不同,不妨$a[x]>b[x]$(小于同理)
我们此时有两种操作,一种是将可操作性得到的转化为得到$x$,然后给出$x?1$,也就是$b[x?1]?1,b[x]+1,a[x?1]+1$.还有一种操作就是将可操作性的给出转化为给出$x+1$,得到$x$,也就是$a[x]?1,b[x]+1,a[x+1]+1$.其实从贪心角度,我们显然是不希望使用第二种操作的,因为第二种操作将会影响我们之前的决策.考虑如果我们使用了第二种操作会发生什么,为了解决$a[x+1]$多出来的1,我们会继续使用第一种操作将其继续转化,然后把1给前面位置?这样递归下去可以发现我们是无法解决的.那么我们需要使用第二种操作,此时我们会发现我们会将之前的$b[x]+1$使用掉了.也就是此时对于当前位并没有解决问题.

下面是具体的代码部分($Hard$版本):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {
	int T=read();
	while(T--) {
		int n=read();
		int sum=0;
		for(int i=1;i<=n;i++) {
			a[i]=read();
			sum+=a[i];
		}
		if(sum%n!=0) {
			cout<<"NO"<<endl;
			continue;
		}
		sum/=n;
		map<int,int>mp1;map<int,int>mp2;//给出,得到
		map<int,int>tot1,tot2;//给出,得到
		int flag=0;
		for(int i=1;i<=n;i++) {
			int num=abs(a[i]-sum);
			vector<int>v;int cnt1=0;
			for(int j=0;j<=32;j++) {
				if(num&(1ll<<j)) {
					cnt1++;
					v.push_back(1);
				} 
				else {
					v.push_back(0);
				}
			}
			int temp=0;int ft=int_INF,ed=-int_INF;
			for(int j=0;j<v.size();j++) {
				if(v[j]==1) {
					ft=min(ft,j);ed=max(ed,j);
					while(j+1<v.size()&&v[j+1]==1) {
						j++;
						ft=min(ft,j);ed=max(ed,j);
					}
					temp++;
				}
			}
			if(temp>=2) {
				flag=1;break;
			}
			if(cnt1==1) {
				if(a[i]<sum) {
					mp2[ft]++;
					tot2[ft]++;
				}
				else {
					mp1[ft]++;
					tot1[ft]++;
				}
			}
			else {
				if(a[i]<sum) {
					mp1[ft]++;
					mp2[ed+1]++;
				}
				else if(a[i]>sum){
					mp1[ed+1]++;
					mp2[ft]++;
				}
			}
		}
		if(flag) {
			cout<<"NO"<<endl;
		}
		else {
			for(int i=32;i>=0;i--) {
				if(mp1[i]!=mp2[i]) {
					while(mp1[i]>mp2[i]) {
						if(tot2[i-1]) {
							tot2[i-1]--;mp2[i-1]--;
							mp2[i]++;mp1[i-1]++;
						}
						else {
							flag=1;break;
						}
					}
					while(mp1[i]<mp2[i]) {
						if(tot1[i-1]) {
							tot1[i-1]--;mp1[i-1]--;
							mp1[i]++;mp2[i-1]++;
						}
						else {
							flag=1;break;
						}
					}
				}
			}
			if(flag) cout<<"NO"<<endl;
			else cout<<"YES"<<endl;
		}
	}
	return 0;
}