一個經典的問題：給定n個數，求其中的任意一個子集滿足集合中的每個元素值加和正好是n的倍數。剛開始怎么也沒有思路，因為n很大，直接搜索顯然是不行的。后來在組合數學書上找到了這個例題（暈，之前白看了，居然把這個經典的題目都給忘了），是抽屜原理的典型應用。
假定n個數為a1，a2，...，an，前n項和分別是S1、S2、...、Sn，那么如果有一個Si模n是0，就是答案，否則，n個數模n的余數只能在1到n - 1之間，把余數作為抽屜，顯然n個數放到n - 1個抽屜里面，肯定有兩個數余數相等，這樣取它們的差就得到了結果，算法復雜度是O(n)的。
抽屜原理的應用都十分巧妙。還有一個例子，一個屋子里面有n個人，他們的最大年齡不超過k歲，問是否肯定存在2組人（兩組沒有重復的人），使得這兩組人的年齡和相等。n個人的組合一共有2 ^ n種方法，注意到最大情況n的人的年齡和是n * k，這樣如果2 ^ n > n * k，根據抽屜原理，一定存在兩種組合他們的年齡和相等，而且沒有重復的人（如果重復，把那個人刪去就行了）。所以O(1)的時間就判斷出了結果。
不過在最開始做題目（PKU 2356）的時候，雖然代碼很短，但是錯了好多次。首先是數組開小了，然后發現輸出的時候題目要求的是輸出數但是我給輸出下標了。最后的問題出在一個很關鍵的地方，在取模為零的時候，我本應該直接就記錄產生了解，但是我以為取模為零的時候下次肯定會產生重復的標記，就沒有特殊處理。其實如果第一個數取模就是0的話，就有可能后面不產生重復的標記，這樣我的程序就錯了，還有就是最后一個是取模為零的時候也會出問題。想了很久才想到這個問題，改正之后終于過了。以后寫程序要仔細，不能想當然啊。
附PKU 2356代碼：
#include <cstdio>
const int N = 10010;
int main()
{
int a[N], n, mod[N] = {0}, tmp = 0, len = 0, pos;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (len) continue;
tmp = (tmp + a[i]) % n;
if (tmp == 0)
{
len = i;
pos = 1;
}
if (mod[tmp])
{
len = i - mod[tmp];
pos = mod[tmp] + 1;
}
else
mod[tmp] = i;
}
printf("%d\n", len);
for (int i = 0; i < len; i++)
printf("%d\n", a[pos+i]);
return 0;
}
posted on 2009-06-12 09:09
sdfond 閱讀(580)
評論(2) 編輯 收藏 引用 所屬分類:
Algorithm - Combinatorics