原文链接https://www.cnblogs.com/zhouzhendong/p/SRM500-250.html

SRM500 Div1 250

题意

（看题用了半个小时……）

有 n 个人（编号从 0 到 n-1）玩游戏，要通过投票的方式确定谁输。现在已知有一些人有明确的意见，认为谁输。具体地用一个 vector decision 来描述，vector decision 的大小可能不足 n 。

定义一个集合 S 包含一些人，初始的时候集合 S 包含所有人。他们会进行若干轮投票，每一轮中，一次进行下列三个过程：

对于所有 **意见明确且认为该输的人在 S 中 ** 的意见，进行投票。
对于剩下的所有的投票机会，每次随机选择一个在 S 中且当前票数最少的人进行投票。
将 S 更新为 S 中票数最多的人构成的集合。如果 |S| = 1 ，那么结束游戏，这个属于 S 的人输了。

给定 n, decision ，返回所有人输的概率的最大值。

\(2\leq n\leq 500, 1\leq decision.size()\leq \min(n,50)\)

一直在想如何求解残局。

事实上，在第一轮中，就可以得到一些重要性质：

第一轮所有人都有且仅有一票。
否则，必然存在一些人的票数大于 1，那么下一轮剩下的人一定是票数最多的所有人的。于是，我们只需要判定是否有解，如果有，那么答案就是 \(\frac 1 {人数}\) ，否则答案就是 0 。

static const int N=505;

int n,t[N];

double probabilityToLose(int N, vector <int> d){

	n=N;

	memset(t,0,sizeof t);

	for (auto v : d)

		t[v]++;

	int Max=0;

	for (int i=0;i<n;i++)

		Max=max(t[i],Max);

	if (Max<=1)

		return 0;

	int tot=0;

	for (int i=0;i<n;i++)

		if (t[i]==Max)

			tot++;

	double res=1.0/tot;

	while (1){

		if (!tot)

			return 0;

		if (tot==1)

			return res;

		tot=n%tot;

	}

}

巴特西

TopCoder SRM500 Div1 250 其他

SRM500 Div1 250

题意

最新文章

热门文章