HDU-1205-吃糖果-鸽巢原理

HDU-1205-吃糖果-鸽巢原理

传送门

这道题是一道组合问题。
鸽巢原理的运用（鸽巢原理又被称为抽屉原理）
即：把n+1个物体放进n个盒子，至少有一个盒子包含两个或者更多的物体
我今天碰到一个组合问题直接卡住了，于是我就来练习组合了。

中文题面我就不描述啦~

本题思路：
一般使用”隔板法“求解。
找出最多的一种糖果，把它的数量N看成N个隔板，隔成N个空间（把每个隔板的右边看成一个空间）
比如：

• case1:
  如果S < N - 1，把S个糖果放在隔板之间，这N个隔板不够放，必然至少有两个隔板之间没有糖果，由于这两个隔板是同一种糖果，所以无解。
  （为啥是N - 1作为边界呢？因为比如上面这个图N = 3的情况下，我们只需要2个糖果就可以恰好满足要求了呀~所以举个例子就知道边界条件了）

• case2:
  当S >= N - 1时，肯定有解。其中一个解时把S个糖果排成一个长队，同种类型的糖果时挨在一起的，然后每次取N个糖果，按顺序一个一个放在N个空间中，由于隔板的数量一定比每一种的糖果数量都多，所以不可能出现有两个同样的糖果放进一个空间的情况。把S个糖果放完，就是一个解。

好啦~我说完啦
这道题只需要你输出Yes或者No即可

代码部分：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

ll a[N];
ll n;
int flag;
ll ans;

bool cmp(ll a, ll b)
{
	return a > b;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		flag = 0;
		ans = 0;
		scanf ("%I64d", &n);
		for (int i = 0; i < n; i++)
		{
			scanf ("%I64d", &a[i]);
			ans += a[i];
		}
		sort(a, a + n, cmp);
		ans -= a[0];
		if (ans < a[0] - 1)
		{
			flag = 1;
		}
		flag ? cout << "No\n" : cout << "Yes\n";
	}
	return 0;
}