[Educational Codeforces Round 32][Codeforces 888E]Maximum Subsequence
[Codeforces Round #445][Codeforces 886E]Maximum Element

[Codeforces Round #445][Codeforces 886C]Petya and Catacombs

Zarxdy34 posted @ 2017年11月13日 09:06 in Codeforces with tags 贪心 , 192 阅读

    题意:在一个完全图中(且每个点都有自环)从任意点出发,到达一个点时记录上一次到达这个点的时间,如果第一次到达这个点则记录下小于当前时间的随机数。给出记录下来的n个数,求图的最少点数。

    题解:设第i个数为\(x_i\),从\(x_i\)到i连一条边。可以发现图中有n+1个点(包括0号点),n条边,正好构成了一棵树。容易发现在同一个点上走的方案对应树上的一条向根走的路径。题目即求最少的指向树根的链数使得这些链完全覆盖了n+1个点。

    显然答案即为叶子节点个数,因为一条这样的链最多只能覆盖到一个叶子节点,所以答案大于等于叶子节点数;而从每个叶子节点出发向根走直到不能继续走为止,刚好能覆盖所有点。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int d[maxn];
int n;
int ans;

int main()
{
	scanf("%d",&n);
	for (int i=1,x;i<=n;i++) scanf("%d",&x),d[x]++;
	for (int i=1;i<=n;i++) if (d[i]==0) ans++;
	printf("%d\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter