【鸽巢定理】POJ

xiaoxiao2021-02-28  59

/* 题意:给出n个数,任选几个数,使其和为n的倍数。 鸽巢原理 sum[i]=sum[1]+sum[2]+...sum[i]; 如果不存在sum[i]%n==0的情况 i:1->n sum[i]%n必然存在[1,n-1] 然而有n个数 所以必然存在i<j sum[i]%n==sum[j]%n 等价于 (sum[i]-sum[j])%n==0 即区间i->j的和为n的倍数 如果存在sum[i]%n==0 输出1->n的数 */ #include <cstdio> #include <cstring> using namespace std; int sum[100010],v[100010],a[100010]; int main() { int n,x; scanf("%d",&n); sum[0]=0; memset(v,-1,sizeof(v)); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); sum[i]=(sum[i-1]+a[i])%n; } v[0]=0;/*不加这句 测试数据3 1 4 7*/ for(int i=1; i<=n; i++) { int index=sum[i]; if(v[index]==-1) v[index]=i; else { printf("%d\n",i-v[index]); for(int j=v[index]+1; j<=i; j++) printf("%d\n",a[j]); break; } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-42783.html

最新回复(0)