11237 - Halloween treats

题目链接

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

思路：c <= n 这个条件很关键，如果有这个条件，那么就可以开一个sum[i]记录0 - i的前缀和%c的值，这样一来在长度n的数组中，必然会出现重复的两个值，用sum[i] - sum[j] == 0这个区间就必然是所求的答案

代码：

#include 
  
   
#include 
   
     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; }