题意
有 \(n\) 个人,第 \(i\) 个人手上最初有 \(a_{i}\) 颗糖。现在每个人可以把自己手中的糖选一些给不多于一个人,同时每个人也只能接受不多于一个人的糖,选出的糖的数量必须是二的次幂。问能否能让每个人最终手上的糖的数量相等。
思路
首先,这道题与简单版的区别在于:这道题可以选择不给其它人糖。换句话说,如果你需要得到 \(2^{x}\) 颗糖,你除了可以选择得到 \(2^{x+1}\) 颗糖,给出 \(2^{x}\) 颗糖,还有了一种新的选择:直接得到 \(2^{x}\) 颗糖。而简单版则只能选择前者,因为题目要求你必须给出一次糖。
然后考虑如何解决。首先平均数不是整数或者 \(a_{i}-mean\) 的值在二进制表示下下 \(1\) 的个数不符合题目要求的话直接判断为无解。然后我们发现上述的这两种选择的本质区别其实就是 \(x\) 的个数和 \(x+1\) 的个数的变化,且变化只针对相邻的两个数值,所以可以考虑贪心。我们先假设每次都先选第二种情况,最后再来调整。记录三个数组 \(cnt,add,del\) 分别表示 \(x\) 得到的次数(如果是负数则为给出),\(x\) 最多可以再被多选几次,\(x\) 最多可以再被多给出几次。
得到这三个数组之后再来调整每一个 \(cnt\) 的值,判断每一个数,看 \(cnt_{i}\) 的正负,奇偶性。如果为奇数的话一定无解,因为每一次操作 \(x\) 的数量一定会增加或减少 \(2\) 的倍数个,因为从给出 \(2^{x}\) 颗糖变成了得到 \(2^{x}\) 颗糖。如果为偶数的话就用 \(add\) 或者 \(del\) 来调整即可。如果 \(add\) 或者 \(del\) 出现了不够的情况时说明了无解。注意:如果 \(cnt_{i}\) 加上了 \(k\),那么 \(cnt_{i+1}\) 就要减去 \(k \div 2\),反之亦然。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
const int MAXM = 30 + 10;
int cnt[MAXN],T,n,a[MAXN],sum,mean,add[MAXM],del[MAXM];
inline int Lowbit(int x){return x & -x;}
inline bool check()
{
for(int i = 0;i <= 31;i++) add[i] = del[i] = cnt[i] = 0;
for(int i = 1;i <= n;i++)
{
int now1 = Lowbit(abs(a[i] - mean));
int now2 = abs(a[i] - mean) + now1;
if(Lowbit(now2) != now2) return false;
if(a[i] - mean > 0) cnt[__lg(now1)]--,cnt[__lg(now2)]++;
if(a[i] - mean < 0) cnt[__lg(now1)]++,cnt[__lg(now2)]--;
int tmp = __builtin_popcount(abs(a[i] - mean));
if(a[i] - mean > 0 && tmp == 1) add[__lg(now1)]++;
if(a[i] - mean < 0 && tmp == 1) del[__lg(now1)]++;
}
for(int i = 0;i <= 30;i++)
{
if(cnt[i] % 2 != 0) return false;
if(cnt[i] < 0)
{
if(add[i] * 2 < -cnt[i]) return false;
cnt[i + 1] -= -cnt[i] / 2;
}
if(cnt[i] > 0)
{
if(del[i] * 2 < cnt[i]) return false;
cnt[i + 1] += cnt[i] / 2;
}
}
return true;
}
signed main()
{
cin >> T;
while(T--)
{
cin >> n;sum = 0;
for(int i = 1;i <= n;i++) cin >> a[i],sum += a[i];
mean = sum / n;
if(sum % n != 0){puts("No");continue;}
if(check() == true) puts("Yes");
else puts("No");
}
return 0;
}
标签:__,lg,cnt,int,题解,Hard,del,Party,mean
From: https://www.cnblogs.com/Creeperl/p/17913430.html