关于HDOJ 1205题(吃糖果) 的理解(C/C++)

    好吧，拿到这个题的时候并没有考虑到抽屉的思想，之前也没遇到过关于抽屉（鸽巢）原理（原谅我题做少了，算法数据结构什么的太弱鸡）。 然后默默地打开了百度……
    emmm？抽屉原理？？什么鬼
    好吧，所以最后AC之后来记录一下，当个笔记的形式吧

---

题目描述

吃糖果
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 54502 Accepted Submission(s): 15562

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

Hint
Hint

Please use function scanf

Author
Gardon

---

原题链接

More info:Question

---

抽屉原理

以下来自百度百科


桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放两个苹果。这一现象就是我们所说的“抽屉原理”。

抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。”

抽屉原理有时也被称为鸽巢原理。

第一抽屉原理

原理1： 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。

证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的n+k(k≥1)，故不可能。




原理2 ：把多于mn(m乘n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。

证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。




原理3 ：把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。







原理1 、2 、3都是第一抽屉原理的表述。

第二抽屉原理

把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体(例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。

---

Accepted代码

思路的话，重点在于把最大的那一种糖果单独拉出来，把它当做抽屉，那么只要剩余的糖果总数不少于抽屉数-1，那么就可以依照从大到小的顺序，依次放进抽屉，在满足条件要求下，也就是在相邻糖果不同的前提下放完（吃完）这些糖果了。由于抽屉是最大的，所以第一轮放入以内总能放完第二大的糖果，也就是说第二大的糖果不可能出现在第三轮放入时，所以第二大的糖果不可能相邻，第三大的糖果同第二   ……  如此，最后放完之后可以把放在抽屉之内的糖果看成是抽屉之间的隔板，隔板彼此之间相邻的不可能同种类，抽屉不可能相邻（因为有隔板），以上，满足条件啦。

#include<iostream>
#include<algorithm>
using namespace std;
int n, ans[1000005],t;
bool cmp(int a, int b) { return (a > b ? true : false); }
int main()
{
    cin >> t;
    while (t--) {
        long long int sum = 0;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> ans[i];
            sum += ans[i];
        }
        sort(ans, ans + n,cmp);
        if (sum - ans[0] >= ans[0]-1) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

---

参考博客 claireyuancy

以下是 claireyuancy 老哥的代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main()
{
    __int64 i,n,sum,max,temp;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;max=-1;
        scanf("%I64d",&n);
        for(i=0;    i<n;    i++)
        {
            scanf("%I64d",&temp);
            sum+=temp;
            if(temp>=max)
            {
                max=temp;    
            }
        }
        if(max-(sum-max)<=1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}