【题目描述】

【输入描述】

【输出描述】

对于每组数据，输出一行，包含一个“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,就能保住相邻两个板直接有糖果（每组至少两个或者最后一组是一个），如果不能满足，那么就相当于板少了，两个糖果靠在一起了。不满足题意了。

(adsbygoogle = window.adsbygoogle || []).push({});