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;
}

相關日誌