现在的位置: 首页 > 综合 > 正文

POJ 3370 Halloween treats(鸽巢原理)

2019年02月12日 ⁄ 综合 ⁄ 共 939字 ⁄ 字号 评论关闭

首先了解到鸽巢原理: 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。

可以推出一个结论:任意n+1个数,必有一段连续的数字之和是n的倍数。

先预处理出一个前缀和,假设到i时,前缀和也模n不为0,要加上的第i+1个数模n也不为0(为0那么答案为这个数),于是容易得出到i+1时的前缀和模n的结果必定与为i时的结果不相同。如果到j时的前缀和模n与到i时相同,那么从i+1到j的所有数的和必为n的倍数。显然是存在这样的解,因为模n的结果最多只有n个,其中为0时又正好是解。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;
int s[maxn], tag[maxn], id[maxn];
bool rema[maxn];

bool cmp(int a, int b)
{
        return s[a] < s[b];
}

int main()
{
//        freopen("A.in", "r", stdin);

        int c, n, sum;
        while(~scanf("%d%d", &c, &n) && c)
        {
                bool flag = false;
                for(int i = 0; i < n; i++)
                {
                        scanf("%d", &s[i]);
                        id[i] = i;
                }
//                sort(id, id + n, cmp);
                sum = 0;
                memset(rema, false, sizeof(rema));
                rema[0] = true, tag[0] = -1;
                for(int i = 0; i < n; i++)
                {
                        sum += s[id[i]];
                        sum %= c;
                        if(rema[sum])
                        {
                                printf("%d", id[tag[sum] + 1] + 1);
                                for(int j = tag[sum] + 2; j <= i; j++)
                                        printf(" %d", id[j] + 1);
                                printf("\n");
                                flag = true;
                                break;
                        }
                        rema[sum] = true;
                        tag[sum] = i;
                }
                if(flag)
                        continue;
//                else
//                        printf("no sweets\n");
        }
        return 0;
}

抱歉!评论已关闭.