鸽巢原理,或称抽屉原理:把n+1个物体放进n个盒子,至少有一个盒子包含连个或更多的物体。

典型例题:

1.hdu 1205 吃糖果

小G有k种糖果,每种数量已知,小G不喜欢连续两次吃同样的糖果,问有没有可行的方案。

分析:找出最多数量的糖果,把它的数量N看成N块隔板,剩余所有糖果的数量为S。若两块隔板不能连续,则两块隔板之间必有一颗糖果。所以,只需判断S是否大于等于(N-1)即可。

#include <iostream>
 using namespace std;
 typedef long long ll;
 int main(){
     int t;
     cin>>t;
     while(t--){
         int n;
         cin>>n;
         ll num,minx=-1,s=0;
         while(n--){
             cin>>num;s+=num;
             if(num>minx)
             minx=num;
         }
         if(minx-1>(s-minx))
         cout<<"No"<<endl;
         else cout<<"Yes"<<endl;
     }
 }
View Code

2.hdu 1808

大致题意:n个邻居有n堆数中,问是否存在一些数,能否被C这个数整除。(C<n)

分析:此题根据抽屉原理,t表示前k的前缀和对C的取余的结果,s[t]=k记录此时的位置。当后面第m项出现相同的余数时,k+1项到m的和定是C的倍数,输出答案即可。

#include <iostream>
 #include <string.h>
 using namespace std;
 typedef long long ll;
 int f[100005],a[100005];
 int main(){
     int c,n;
     while(scanf("%d %d",&c,&n)){
         if(c==0&&n==0)break;
         memset(f,-1,sizeof f);
         ll s=0;
         for(int i=0;i<n;i++){
             scanf("%d",&a[i]);
         }
         for(int i=0;i<n;i++){
             s+=a[i];
             int t=s%c;
             if(t==0){
                 for(int j=0;j<=i;j++){
                     j==0?printf("%d",j+1):printf(" %d",j+1);
                 }
                 printf("\n");
                 break;
             }
             else if(f[t]!=-1){
                 for(int j=f[t]+1;j<=i;j++)
                 j==f[t]+1?printf("%d",j+1):printf(" %d",j+1);
                 printf("\n");break;
             }
             f[t]=i;
         }
     }
     return 0;
 }
View Code
01-16 22:15