吃糖果(鸽笼原理) - HDU 1205

鸽笼原理（也称抽屉原理） 简单的表述如下，这个原理看起来非常通俗，好像是在说一句废话一样，然而数学就是这样，总是需要证明一下。

证明是用反证法：假设每个笼子只有一个鸽子，那么必定有一个鸽子不在笼子里，和原命题冲突。

另外还有一个拉姆齐定理，英文是Ramsey定理，是鸽笼原理的扩展，鉴于拉姆齐定理比较难懂，就不深入讲解了，Ramsey定理的证明是数学界里难度非常高的证明题。

若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。

（9个笼子10只鸟）

题目：

Problem Description

HOHO，终于从Speakless手上赢走了所有的糖果，Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下。

Input

第一行有一个整数T，接下来T组数据，每组数据占2行，第一行是一个整数N（0<N<=1000000)，第二行是N个数，表示N种糖果的数目Mi(0<Mi<=1000000)。

Output

对于每组数据，输出一行，包含一个"Yes"或者"No"。

Sample Input

2

3

4 1 1

5

5 4 3 2 1

Sample Output

No

Yes

先思考1分钟

......

解题思路：

1、由于Gardon吃糖需要先吃一颗类型为X的，再吃一颗类型为Y的，对于任意类型的糖果，需要能够用其他糖果隔开。

2、把某种糖果看做隔板,如果某种糖果有n个，那么就有n块区域，至少需要n-1块其他种糖果才能使得所有隔板不挨在一块，也就是说能吃完这种糖果.至少需要其他种类糖果n-1块。(鸽巢原理)

3、这里面只要考虑到，对于数量最多的糖果来说，需要有一定数量的其他糖果来隔开。

源代码：G++ 280ms

#include<stdio.h>
#include<stdint.h>

int main()
{
    //输入次数
    int count;

    scanf("%d", &count);

    while (count--)
    {
        //糖果中数量的最大值
        int max_value = -1;
        //糖果种类数量
        int sugar_type_count;
        //糖果总数
        int64_t sum = 0;

        scanf("%d", &sugar_type_count);

        for (int i = 0; i < sugar_type_count; i++)
        {
            int suger_count;

            scanf("%d", &suger_count);

            sum += suger_count;
            //更新最大值
            if (max_value < suger_count)
                max_value = suger_count;
        }

        //剩余糖果大于等最大值-1
        //如11颗糖，其中一种有6颗，别的颜色有5颗，正好可以隔开这6颗糖
        if ((sum - max_value + 1) >= max_value)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}