抽屉原理

抽屉原理亦称鸽巢原理，该原理可由三种形态描述。

抽屉原理1：把n+1个元素放入n个集合内，必定有一个集合至少含有两个或两个以上元素。

抽屉原理2：把m个元素放进n个集合内，至少有一个集合含有k个元素，其中 k=m/n (n整除m)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　k=[m/n]+1 (n不整除m)。

抽屉原理3：把无穷多个元素放进有限个集合，必然至少有一个集合里有无穷多个元素。

例题：POJ 2356

Find a multiple

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9946		Accepted: 4245		Special Judge

Description

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).

Input

The first line of the input contains the single number N. Each of next N lines contains one number from the given set.

Output

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.

If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.

Sample Input

Sample Output

2
2
3

分析：

本题巧妙利用了鸽巢原理。

依题意，我们有n个数，而这n个数模n会有n种结果，但是除去恰好可以整除n的那些数后，模n的余数只有1~n-1。

设sum[i]为一维数组前缀和，那么我们把得到的n个sum[i]记为元素，n-1个余数作为抽屉，必然会有一个抽屉里至少有两个元素，记为sum[i]=sum[j],i>j。

因为sum[i]%n=sum[j]%n,那么(sum[i]-sum[j])%n=0，即：a[i],a[i+1],.....a[j]为所取元素。

AC code:

#include<cstdio>
#include<algorithm>
using namespace std;
int a[10010];
int sum[10010];
int mod[10010];
void print(int s,int t)
{
    printf("%d\n",t-s+1);
    for(int i=s;i<=t;i++)
        printf("%d\n",a[i]);
}
int main()
{
    freopen("input.txt","r",stdin);
    int n;
    scanf("%d",&n);
    fill(sum,sum+n+1,0);
    fill(mod,mod+n+1,0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[1]=a[1];
        sum[i]=sum[i-1]+a[i]; 
    }
    for(int i=1;i<=n;i++)
    {
        if(sum[i]%n==0)
        {
            print(1,i);
            break;
        }
        else if(!mod[sum[i]%n])
        {
            mod[sum[i]%n]=i; 
        }
        else
        {
            print(mod[sum[i]%n]+1,i);
            break;
        }
    }
    return 0;
}

View Code

抽屉原理

推荐阅读