HDU ACM 1205 食糖果

HDU ACM 1205 吃糖果

解析：

1、首先假设两种糖果，其中一种数量最大为n，要想这两种糖果交替吃完，另一种糖果最少应为n-1；n个糖果排成一排，内部共有n-1个空，分离相邻的两个相同的糖果。题中，找出某种糖果的最大数量max，则至少需要max-1个糖果（即除去最大数量剩下的总和）去填充空隙。若剩下糖果数大于max也是可以的，我们可以想成把数量较少的糖果用来“加厚”原来的空隙（即再把他们填到最大数量糖果的空隙中，可以两个或两个以上不同的糖果去填充同一个空隙）。因此需满足sum-max>=max-1;即sum-max+1>=max。即剩余的糖果总数要比max-1多或等于。

#include<iostream>   
using namespace std;

int main()  
{ 
	__int64 sum,max;
	int i,T,n,m;

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		sum=0;
		max=-1;
		for(i=0;i<n;i++)
		{
			scanf("%d",&m);
			sum+=m;
			if(max<m)
				max=m;
		}
		if(sum-max+1>=max) puts("Yes");
		else puts("No");

	}
    return 0;  
}