USACO MAR08 Gold Pearl Pairing 珍珠分對
本文正體字版由OpenCC轉換
如果隨機配對的話，會出現到最後有剩餘的珍珠無法配對的情況。我們可以考慮順序配對，即把每個珍珠按照輸入顏色順序排在一個數組中，讓第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;
}
上次修改時間 2017-02-03