鸽巢原理

1. 将 n + 1 个物品放入 n 个箱子里面， 则至少有一个箱子里面含有两个或两个以上的物品

2. 当 n 只鸽子飞进 m 个巢中，必定至少有一个巢中飞进去了 r = [ ( n - 1 ) / m ] + 1 个鸽子

例1

Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，
喜欢先吃一种，下一次吃另一种，
这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？

eg ： n种糖果 分别有 2 3 4 6 7 8

sum = 2 + 3 + 4 + 6 + 7 + 8 = 30 ; S = sum - maxn; N = maxn = 8;

我们可以令 N 是鸽巢， S是鸽子， 我们现在要将S个鸽子都放入鸽巢中，每种用不同的符号表示， 如下表所示：

1. S >= N - 1 : 如上表所示，可以满足题意，这么吃糖果，不会重复
2. S = N - 1 : 正好最后一个鸽巢空下，但也不会重复
3. S < N - 1 ：将会有多余的鸽巢空下， 则有相同的糖果会放在一起吃

因此，本题只需要判断S 和 N -1 之间的关系即可

因此 我们可以粗略想为 ： 当 鸽子 比 鸽巢 多的时候 就一定可以将其表示为上表所示，并且每相邻的两个一定不是一个种类的

例2

有n种不同的小球，每种小球有ai个，每次选两个不同种类的小球丢弃，直到盒子为空或者只剩下一种颜色的小球。求每种颜色的小球是否为最终可能被剩下的颜色

#define int long long
const int N = 1e5 + 10;
int a[N], b[N];
void solved()
{
    int n, sum = 0; 
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> a[i], b[i] = a[i], sum += a[i];
    sort(b, b + n);

    if(n == 1)  //特判
    {
        cout << 1 << endl;
        return;
    }

   //找最大值和次大值，次大值用于当a[i] == m1时，次大值充当最大
    int m1 = b[n - 1], m2 = b[n - 2], mx;

    for(int i = 0; i < n; i ++)
    {
        if(a[i] == m1) mx = m2;
        else mx = m1;

        // sum - mx - a[i] 是鸽子， mx - 1是鸽巢， 
        // 该情况是 鸽巢不会有多余的，
        /* sum - a[i]我们可以理解为我们将剩下的给鸽巢原理了，
        和上面吃糖一个道理，不会有相同种类的两个是挨着的，
        因此我们，只需要判断奇偶即可，如果a[i]比取模后的数大，
        就证明有剩余的  */
        if(sum - mx - a[i] >= mx - 1)
        {
            if(a[i] > ((sum - a[i]) % 2))
                cout << "1 ";
            else cout << "0 "; 
        }
        else
        {
        // 该情况是 鸽巢有多余的
        // 剩余鸽巢：2 * mx - sum + a[i]) 是由 鸽巢 - 鸽子 而来
        // 如果 a[i] 比剩余的鸽巢还多，证明有可能留下
            if(a[i] > (2 * mx - sum + a[i]))
                cout << "1 ";
            else cout << "0 ";
        }
    }
    cout << endl;
}

法二

    if(n == 1) cout << 1 << endl;

    // 所有数的和 都比 最大值小 或 相等
    else if(sum - m1 < m1) cout << 1 << endl;
    else if(sum - m1 == m1) cout << 0 << endl;
    else
    {
        // 鸽子多，鸽巢少 鸽巢原理
        int ans = 0;
        for(int i = 0; i < n; i ++)
            if(a[i] > (sum - a[i]) % 2) ans ++;
        cout << ans << endl;
    }