hdu 1205面白い小題2種類の解法鳩の巣の原理

あめを食べる
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 12122    Accepted Submission(s): 3530
Problem Description
HOHO、ついにSpeaklessの手からすべてのキャンディに勝って、Gardonがキャンディを食べる時特殊な癖があって、同じキャンディを一緒に食べるのが好きではありませんて、先に1種を食べるのが好きで、次は別の種を食べて、このようにします;しかし、Gardonはキャンディを食べる順番があるかどうか分からない.彼はすべてのキャンディを食べ終わることができるのだろうか.プログラムを書いて計算してください.
 
Input
1行目には整数Tがあり、次にT組のデータが2行を占め、1行目は整数N(0 
Output
データのセットごとに、「Yes」または「No」を含む行を出力します.
 
Sample Input

   
   
   
   

    
    
    
    2
3
4 1 1
5
5 4 3 2 1
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    No
Yes


    
    
    
    
 
     
 
      Hint 
     
Hint 
    
    
    
    
     
Please use function scanf
   
   
   
   

 
Author
Gardon
/*もし最大の山-次の山<=1ならば、问题はきっと解があります:私达は最大と次の大きい中から毎回1つを持つことができて、それから彼らが第3の山と等しい时を待って、毎回3つの山の中からそれぞれ1つを持って、彼らが第4の山と等しい时を待って、毎回4つの山の中からそれぞれ1つを持って、このようにずっとすべての山を持ち终わります.-二次ヒープ<=1ですので、前に二次ヒープ以外のヒープから取って、最大ヒープを減らすことができます.最大ヒープ-二次ヒープ<=1に減らすことができれば、元の問題は解決します.減らすことができるかどうかは、sum-max-max 2>=max-max 2-1が成立しているかどうか、sumが総和で、maxが最大ヒープで、maxが二次大です.整理:2*max-sum<=1*/#include int main() {     int cas,n,max;     scanf("%d",&cas);     while(cas--)     {         __int64 sum;         sum=max=0;         scanf("%d",&n);         while(n--)         {             int num;             scanf("%d",&num);             if(maxもう一つはハトの巣の原理です
1.あるキャンディを仕切り板と見なし、あるキャンディがn個あれば、n+1個の領域があり、少なくともn-1個の他の種類のキャンディが必要で、すべての仕切り板が一つにならないようにする.つまり、このキャンディを食べ終わることができる.少なくとも他の種類のキャンディn-1個が必要である.(ハトの巣の原理)
2.最も数の多いキャンディ(仕切り板)は最も多くの空間を作ることができ、もしこのキャンディがmaxn個あるならば.....maxn-1個の他のキャンディが必要である.ある数のmaxnより少ないキャンディにとって、もともと数の最も多いキャンディ構造の仕切り板の上で元の仕切り板を「厚くする」ことができて.....では、この「あるキャンディ」は姿を消してしまう.....
极端な状况を考える.あるキャンディがこのmax n+1の空间に条件を満たすシーケンスを构筑できない场合,このキャンディは少なくともmax n+1+1个(2种类のキャンディしかない场合を考える)…(鸠巣原理)….しかしこれは最も数の多いキャンディがmax n个しかないことと矛盾する…(max n+1+1>maxnという不等式は理解しにくいだろう…).

#include <iostream>
using namespace std;

int main()
{
 int ncases;
 scanf("%d",&ncases);

 while(ncases--)
 {
  __int64 maxvalue=-1,sweetkinds,sum=0;
  scanf("%I64u",&sweetkinds);

  __int64 i,n;
  for(i=0;i<sweetkinds;i++)
  {
   scanf("%I64u",&n);
   sum+=n;
   if(maxvalue<n)
    maxvalue=n;
  }
  if((sum-maxvalue)>=(maxvalue-1))
   printf("Yes
");
  else
   printf("No
");
 }
 return 0;
}