正如标题所说，这道题是一道鸽巢原理的题（本蒟蒻做之前还不知道什么是鸽巢原理），对于鸽巢原理，可移至这里了解详细。

鸽巢原理

存在n+1只鸽子进入n个鸽巢，那么必定会有一个鸽巢存在两只鸽子。存在n只鸽子进入m个鸽巢，那么必定有一个鸽巢存在r只鸽子

r=[(n-1)/m]+1

对于本题呢，我们可以先看hdu1205

alt

该题是非常典型的鸽巢原理问题。

我们将最多的一种糖果想象成鸽巢，将剩余其他糖果总和想象成鸽子，也就转换成了sum-maxa与maxa的问题

令S=sum-maxa，N=maxa

S个鸽子在一个队列中，相同的鸽子连续在一起排放，将鸽子顺序塞入鸽巢之中，每个鸽巢可以想象成一个链表的表头，S个鸽子依次出队，分别在每个表头下边分配一个，直至S个鸽子分配完全。 alt 可见

对于S>=N-1时肯定有解

我们将N个鸽子按种类排成一个队列，即相同种类的糖果都是紧挨连续排列的

然后每次取N个鸽子，按顺序一个一个地放进N个鸽巢。

不足N个时，按空间顺序，从后往前放。

最坏情况S=N-1时，从左往右放入，若是从右往左放入则会有两个糖果是一样的，导致连续吃到两次糖果

由于任意ai<=N，所以每个鸽巢中不存在相同的鸽子，并且S>=N-1，鸽巢不会连续，所以必然存在解

对于S<N-1时，必然存在两个鸽巢连续，也就是吃到相同的两个糖果，故必然不存在解

对于选择maxa这种糖果进行最优构造鸽巢都冗余其他情况更不合理

所以S<N-1时，不存在解

那么便得到了

void solve()
{
    cin >> n;
    S = N = 0;
    for(int i = 1; i <= n; ++i)
    {
        cin >> x;
        N = max(N, x);
        S += x;
    }
    S -= N;
    cout << (S >= N - 1 ? "Yes" : "No") << endl;
}

而本题糖果和小球同理

对于每一组小球，其中一种小球a[i]来讲，可以用最优方式两两删除除a[i]以外其他小球，剩余小球与a[i]比较，如果小于a[i]说明这种小球有可能剩余，否则不可能剩余（最优方式都未剩余其他方式更不能）

其中最优方式删除就是吃糖果了，如果存在吃糖方案，那么吃的糖总数%2就是剩余糖果数，再与一种比较即可

即如果sum-a[i]-maxa>=maxa-1 那么边比较(sum-a[i])%2和a[i]大小

否则意味着除了a[i]剩下的小球中两两删除无法删到底会剩余最多的那个小球

即maxa-(sum-a[i]-maxa)为剩余小球和a[i]比较 a[i]多则可能剩余否则不可能

注意点：

maxa的求取 maxa为除了a[i]以外数组最大值这说明我们要预处理求出最大值和第二大值当最大值与a[i]是同一个时便选择第二大值（这里可以考虑模拟优先队列）（这里感觉数据有点水，如果第一个值就是最大值有些滚动求解的就不太行）
n=1时需要特判
sum要开long long（本蒟蒻就在这里卡了好久）

最后附ac代码O(t*n)，祝成功

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int INF = 0x7fffffff;
const double eps = 1e-5;

int t,n,a[N];
int max1,max2,maxa,mi;
long long sum=0;

void solve() {
    max1=max2=-INF;
    sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        if(a[i]>max1){
            max1=a[i];//求最大值
            mi=i;
        }
    }
    if(n==1) {//特判1
        cout<<1<<endl;
        return;
    }
    for(int i=0;i<n;i++){
        if(i!=mi) max2=max(max2,a[i]);//求第二大值
    }
    for(int i=0;i<n;i++){//重点 鸽巢原理
        maxa=(max1==a[i])?max2:max1;
        if(sum-a[i]-maxa>=maxa-1) {
            if(a[i]>((sum-a[i])%2)) cout<<1<<' ';
            else cout<<0<<' ';
        }
        else {
            if(a[i]>(2*maxa-sum+a[i])) cout<<1<<' ';
            else cout<<0<<' ';
        }
    }
    cout<<endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

智乃想考一道鸽巢原理

鸽巢原理

r=[(n-1)/m]+1

令S=sum-maxa，N=maxa