1000:ShuffleSort

题意:

Fox Ciel有一副N张牌,0到N-1,包括在其中。对于每一个i,第i个 card有一个写在它上面的整数卡片。卡片上写的整数有可能是相同的。这些卡片是没有区别的。Ciel想要对卡片进行分类。更确切地说,她想把它们在桌子上排成一行,这样卡片上的整数就会形成一个非递减的序列。为了实现这一目标,她将整副牌放入手中,并应用以下过程(从步骤1开始)。

1.她把手里的牌都洗牌了。这等价于随机地对纸牌进行均匀的排列。

2.X是在她手上仍然握着的所有整数中最小的一个。Ciel检查她刚洗过的牌的最上面的牌。如果卡片中包含一个大于X的整数,那么她将继续执行第1步。否则,她把卡片放在桌子上。(如果桌子上已经有一些卡片,新的卡片就会被放置在他们的右边,以扩展出分好的卡片。)在她这样做之后,如果她手里没有更多的牌,她就完成了。否则,她会重复步骤2(不需要洗牌!)
给定向量卡片,返回第1步(洗牌)将在上述排序过程中执行的预期次数。(盆友翻译的鬼畜版)。。。

分析:

一看这个题目,就是反着处理一个dp就好了,很好写。。。我们只需要思考,我们倒着取数的期望就是当前数/相同数+之前数-1。。。然后dp前排个序就好了。。。

代码:

 

double dp[100];
double ShuffleSort::shuffle(vector cards)
{
	sort(cards.rbegin(), cards.rend());
	dp[1] = 1;
	double t = 1;
	for (int n = 2; n <= cards.size(); n++)
	{
		if (cards[n - 1] == cards[n - 2])t = t + 1.0;
		else t = 1.0;
		dp[n] = n / t + (dp[n - 1] - 1);
	}
	return dp[cards.size()];
}

2 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注