CF1868B1 Candy Party (Easy Version)

One_JuRuo · 2023-09-11 08:43:17 · 题解

思路

首先想要均分糖果，那么必须满足糖果总数 sum 是人数 n 的倍数。

然后我们再取平均值，令 s=\frac{sum} n。

因为每个人必须收到一次糖果且只能送出一次糖果，所以对于每一个 a_i，我们首先需要满足 a_i-s 可以被表示为 2^x-2^y。

令 k=|a_i-s|。

以二进制的方式来看，\operatorname{lowbit}(k) 应该就是其中一个二次幂，是给出的还是收到的糖果数要看 a_i 和 s 的大小关系，那么 k+\operatorname{lowbit}(k) 就应该是另外一个二次幂。

所以，如果 k+\operatorname{lowbit}(k) 不是二次幂，就可以肯定无解。

那么我们再统计每个人需要接受和送出的糖果数的个数，如果接受和送出的糖果数的个数也不相等，那么就无解，否则，有解。

其实还有个特殊情况，那就是原本就有的糖与平均数相同，但是思考一下就会发现不影响结果。

我们只需要把原本就有的糖与平均数相同的人放在给糖过程中间，过一下手就好，比如 a 要给 b 一颗糖，而 k 刚好拥有的糖就是平均数，那么只需要让 a 给 k 一颗糖，然后再由 k 给 b 一颗糖就好，可以发现这样增加一个转手的过程不影响答案，并且也满足了 k 的需求，所以原本就有的糖与平均数一样不需要考虑，可以直接忽略

AC code

#include<bits/stdc++.h>
using namespace std;
inline long long lowbit(long long x){return x&(-x);}
long long T,n,a[200005],sum,flag,k,low;
map<long long,long long>m1,m2;
inline bool sol()
{
    scanf("%lld",&n),m1.clear(),m2.clear(),flag=sum=0;//多测记得清空
    for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),sum+=a[i];
    if(sum%n) return 1;
    sum/=n;
    for(long long i=1;i<=n;++i)
    {
        a[i]-=sum;k=abs(a[i]);low=lowbit(k);k+=low;
        if(k!=lowbit(k)) return 1;//直接使用lowbit判断是不是二次幂
        else if(a[i]>0) ++m1[k],++m2[low];
        else if(a[i]<0) ++m1[low],++m2[k];
    }
    for(auto i=m1.begin(),j=m2.begin();i!=m1.end()&&j!=m2.end();++i,++j) if(flag||i->first!=j->first||i->second!=j->second) return 1;//接受和送出的糖果数的个数是否一样
    return 0;
}
int main()
{
    scanf("%lld",&T);
    while(T--)
        if(sol()) printf("NO\n");
        else printf("YES\n");
    return 0;
}