UVA 11237 - Halloween treats(鸽笼原理)

11237 - Halloween treats

题意：有c个小伙伴，n个房子(c <= n)。每一个房子会给ai个糖果，要求选一些房子，使得得到的糖果能平均分给小伙伴，输出方案

思路：c <= n 这个条件非常关键，假设有这个条件，那么就能够开一个sum[i]记录0 - i的前缀和%c的值，这样一来在长度n的数组中，必定会出现反复的两个值。用sum[i] - sum[j] == 0这个区间就必定是所求的答案

代码：

#include <cstdio>

#include <cstring>

const int N = 100005;

int c, n, a[N], sum[N], vis[N];

void solve() {

    memset(vis, -1, sizeof(vis));

    vis[0] = 0;

    for (int i = 1; i <= n; i++) {

	sum[i] = (sum[i - 1] + a[i]) % c;

	if (vis[sum[i]] != -1) {

	    for (int j = vis[sum[i]] + 1; j < i; j++)

		printf("%d ", j);

	    printf("%d\n", i);

	    return;

	}

	vis[sum[i]] = i;

    }

}

int main() {

    while (~scanf("%d%d", &c, &n) && c + n) {

	for (int i = 1; i <= n; i++)

	    scanf("%d", &a[i]);

	solve();

    }

    return 0;

}