uva 11237 - Halloween treats(抽屉原理)

佚名 6年前 (2019-04-10) 随笔 1718人围观抢沙发百度已收录

题目大意：有c个小孩要到邻居家去要糖果。有n户邻居。每户邻居仅仅会提供固定数量的糖果，熊孩子们为了不发生冲突，决定将取来的糖果平均分配，问说取那几家邻居的糖果能够做到平均分配。注意n ≥ c。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解题思路：抽屉原理。求出序列的前缀和，有n个，将前缀和对c取模后。依据剩余系定理肯定是在0~c-1之间的，假设是0那么答案就不用说了，假设两端前缀和同余，则说明中间该段的和是c的倍数。

又由于n ≥ c，对于取0的时候肯定是能够有解的，那么n个数相应c-1个位置。肯定有同余的情况。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 100000;
int a[maxn+5], s[maxn+5], vis[maxn+5];

int main () {
    int c, n;
    while (scanf("%d%d", &c, &n) == 2 && c + n) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(vis, -1, sizeof(vis));

        vis[0] = s[0] = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = (s[i-1] + a[i]) % c;

            if (vis[s[i]] == -1)
                vis[s[i]] = i;
            else {
                for (int j = vis[s[i]] + 1; j <= i; j++)
                    printf("%d%c", j, j == i ? '\n' : ' '); break; } } } return 0; }