[HDU1205]吃糖果 题解（鸽巢原理）

时间：2023-02-06 17:21:24

[HDU1205]吃糖果

Description

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

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

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

Solution

1.分析题目，我们发现是一种简单的排列组合问题，其实是在问数目不是最大的所有糖果能否将数目最大的一种糖果相互隔开；

2.根据鸽巢原理，maxn个糖果至少需要maxn-1个隔板，即只需判断sum-maxn是否大于等于maxn-1即可，整理式子，我们得到判断条件：sum+2≥maxn*2；

3.本体数据量较多建议使用读入优化，数据范围我是用的是unsigned long long,貌似long long也能过；

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

inline unsigned long long rd(){//读优

	unsigned long long x=0;

	bool f=true;

	char c;

	c=getchar();

	while(c<'0'||c>'9')c=getchar();

	while(c>='0'&&c<='9'){

		x=(x<<1)+(x<<3)+(c^48);

		c=getchar();

	}

	return x;

}void check(){

	unsigned long long i,j,n,sum=0,max=0;

	n=rd();

	for(i=1;i<=n;++i){

		j=rd();

		if(j>max)max=j;

		sum+=j;

	}

	if(sum+2>max*2) printf("Yes\n");

	else printf("No\n");

}

int main(){

	unsigned long long i,n;

	n=rd();

	for(i=1;i<=n;++i)check();

	return 0;

}

有关鸽巢原理可以参考我的博客：http://www.cnblogs.com/COLIN-LIGHTNING/p/8439555.html

相关文章