USACO MAR08 Gold Pearl Pairing 珍珠分對
如果隨機配對的話,會出現到最後有剩餘的珍珠無法配對的情況。我們可以考慮順序配對,即把每個珍珠按照輸入顏色順序排在一個數組中,讓第i(1<=i<=N/2)個珍珠與第(N/2-1+i)個珍珠配對即可,最後得出的一定是一個符合條件的解。
我們用反證法來證明這個命題的正確性。
假設第i個珍珠與第N/2+i個珍珠顏色相同,則從第i個到第(N/2-1+i)個之間的所有珍珠的顏色都相同,這一段中這種顏色珍珠的數量爲N/2+1,即這種顏色的珍珠的數量大於N/2,一定無法配成對。這與題中約定的一定有解矛盾,所以原假設不成立,則第i個珍珠與第N/2+i個珍珠顏色一定不相同。
這道題只要求輸出任意解,該算法生成的解爲一個任意解。
其實這道題並不難,只要能分析出珍珠配對的內在規律,還是很容易的。
/*
ID: cmykrgb1
PROG: ppairing
LANG: C++
*/
//使用輸入輸出流會超時的,要用scanf,printf
#include <iostream>
#define MAX 100000
using namespace std;
int N,C, pearl[MAX];
int main()
{
int i,j = 0,m;
freopen("ppairing.in", "r", stdin);
freopen("ppairing.out", "w", stdout);
cin >> N >> C;
for (i = 0; i < C; i++)
{
scanf("%d",&m);
for (;m>=1;m--)
pearl[j++] = i+1;
}
for (i=0; i<N/2; i++)
printf("%d %dn",pearl[i],pearl[N/2+i]);
return 0;
}