poj 2356 Find a multiple(组合数学：鸽巢原理)

本文主要是介绍poj 2356 Find a multiple(组合数学：鸽巢原理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

和poj 3370很像， 但这里只有一个n且对应n个数

根据鸽巢原理是应该存在一个i对应前i项和模n==0

但是题目中说了这n个数可以相同，所以可能存在不等于0的情况

比如：

5

1 5 5 5 5

但此时必然sum%n有重复

同poj 3370一样输出相同两数对应下标之间的数即可

代码如下：

#include <cstdio>
#include <cstring>
#define MAXN 100100
using namespace std;int flag[MAXN];
int a[MAXN];int main(void) {int n, c, sum, tmp;while(scanf("%d", &n) != EOF) {sum = 0;memset(flag, 0, sizeof(flag));for(int i=1; i<=n; ++i) {scanf("%d", &a[i]);}for(int i=1; i<=n; ++i) {sum += a[i];tmp = sum%n;sum %= n;if(tmp == 0) {printf("%d\n%d\n", i, a[1]);for(int j=2; j<=i; ++j)printf("%d\n", a[j]);break;} else {if(flag[tmp]) {printf("%d\n%d\n", i-flag[tmp], a[flag[tmp]+1]);for(int j=flag[tmp]+2; j<=i; ++j)printf("%d\n", a[j]);break;}}flag[tmp] = i;}}return 0;
}

这篇关于poj 2356 Find a multiple(组合数学：鸽巢原理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---