【题解】吃糖果
【题目描述】
【输入描述】
【输出描述】
对于每组数据，输出一行，包含一个“YES”或者“NO”。
【样例输入】
2 3 4 1 1 5 5 4 3 2 1
【样例输出】
NO YES
【样例分析】
样例有两组，第一组有3种，我们假设是ABC，他们的数量分别是4 1 1 ，
【题目分析】
事实上，题目中的要求可以转换为：“不能连续吃两种一样的”。
那么第一组样例，有三种糖果，我们假设是ABC，他们的数量分别是4 1 1，我们尽量沿着不一样的糖果类型开始吃。那么其中一种方式是ABACAA。这种方式明显不行，A类型糖果重复了。尝试下面几种吃法：
ABCAAA BACAAA AAAABC CABAAA ....
无论什么组合，都无法实现“不能连续吃两种一样的”。
尝试第二组样例，有5种糖果，我们假设是ABCDE，他们的数量分别是5 4 3 2 1。开始尝试构造一种顺序，使其满足“不能连续吃两种一样的”
ABABABABACDCDCE
可以满足题目要求，所以输出YES。
或者换一种思路，用抽屉原理的思路考虑：
第一组样例一共三种类型，我们假设３个抽屉（这是最少状态），
因为A有四个，不论怎么放，两个A都会在一块。
如果我们假设有４个抽屉，那么也不符合要求，因为总会有两个抽屉只有一个A，这样就吃到两个一样的了。
那么第二组样例，一共五种类型
可以看出，我们按照不同的抽屉进行存放，可以实现题目要求。
我们开始总结上面出现的抽屉原理：
１.如果想要求解出答案，抽屉的数量应该以最好是数量最多的那种糖果的数量（以数量最多的那种糖果为标准，每个抽屉一个，这样保证了数量最多的糖果不出现在同一个抽屉里），我们假设数量最多的那种糖果的数量是maxM。那么其他糖果的数量一定小于maxM。
比如上面的5 4 3 2 1，数量最多是第一种，我们假设叫A，所以maxM是5。
注：我们暂时不考虑
ABABABABACDCDCE
这种形式。因为题目是求解一种可以实现的形式，所以我们只求出最有可能的满足条件的形式。
2.我们假设n-1种糖果的总数量为sum。现在有maxM个抽屉并放在一起（上一条已经说明为什么最好是maxM个抽屉），那么我们先将maxM个糖果放到maxM个抽屉中，一个抽屉一个。然后再放sum个糖果，从左到右，一个抽屉一个糖果，这样放的过程中每个抽屉的糖果都不会重复。
可以考虑样例 5 4 3 2 1
3. 在第二条的前提下，如果所有的糖果都放到抽屉以后，如果每个抽屉的糖果数量大于等于2，那么在吃糖果的时候不会重复。
举例子：ABCD四种糖果数量分别是3 1 2 2，那么抽屉模型可以用下面的图表示：
那么这种情况是满足不会重复的。
4.在第二条的前提下，如果有一个抽屉有一个 数量最多的那种糖果，而其他的糖果数量都满足大于等于2，也可以吃完。
比我我们的样例 5 4 3 2 1
注：不要选择从最右侧的A开始吃，因为我们始终是在求有没有一种情况满足需求。
如果不满足剩下两个抽屉都大于等于２，也就是说有两个抽屉都只有一个，根据我们放糖果的顺序，那么这两个抽屉里面的糖果都是A，
那么无论怎么吃都不满足题目要求。
总结：
什么样的公式才能总结出第三条和第四条的内容呢？
主要看是谁导致了我们不能吃掉糖果，答案很明显，就是数量最多的那种糖果，我们假设叫A。A剩余的多少决定是否满足要求。
我们再把问题精简化。我们可以去掉多余数据，只剩数量最少的两组数据，我们得到三种基础模型：
第一种第二种是符合题目要求的，第三种是不符合要求的。
已知去除数量最多的那种糖果的n-1种糖果数量是sum。种类最多的糖果的数量是maxM
那么可以用下面这个公式表示：
sum>=maxM-1
那么到此为止，我们总结出了核心部分：输入数据时，只要满足sum>=maxM-1一定能吃完所有的糖果。
【参考代码】
#include<iostream>
using namespace std;
int main()
{
int t,n,maxx=0,mod;
long long sum;
cin>>t; //测试次数
while(t--)
{
sum=0;
maxx=0;
cin>>n; //数据组数
for(int i=1;i<=n;i++)
{
cin>>mod;
sum+=mod; //总数
if(mod>maxx)
maxx=mod; //求出最大值
}
sum=sum-maxx; //去除掉种类最多的那种糖果
if(sum+1>=maxx)
cout<<"Yes";
else
cout<<"No";
}
}实际上这个题目还可以理解成排列组合中的隔板法：
假设数量最多的那种糖果的数量是M。那么要把这些糖果隔开（类似装到抽屉里），那么至少需要M-1个板。
那么，除了数量最多的那种糖果，剩余糖果数量的总和是sum。只要满足sum>=M-1,就能保住相邻两个板直接有糖果（每组至少两个或者最后一组是一个），如果不能满足，那么就相当于板少了，两个糖果靠在一起了。不满足题意了。
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。