Beyond the Void
BYVoid
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;
}

上次修改时间 2017-02-03

相关日志