抽屉原理
抽屉原理亦称鸽巢原理,该原理可由三种形态描述。
抽屉原理1:把n+1个元素放入n个集合内,必定有一个集合至少含有两个或两个以上元素。
抽屉原理2:把m个元素放进n个集合内,至少有一个集合含有k个元素,其中 k=m/n (n整除m)
k=[m/n]+1 (n不整除m)。
抽屉原理3:把无穷多个元素放进有限个集合,必然至少有一个集合里有无穷多个元素。
例题:POJ 2356
Time Limit: 1000MS | Memory Limit: 65536K | |||
Total Submissions: 9946 | Accepted: 4245 | Special Judge |
Description
Input
Output
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
5 1 2 3 4 1
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