CF755F 题解

· · 题解

题目传送门

思路

这道题我们先从 i 往 p[i] 各连一条有向边，可以发现一共 n 个点，n 条有向边，且每个点的出入度都为 1。所以不难想到最后这个图会变成若干个环。

然后我们需要考虑如何最大化收不到礼物的人数：

  1. 对于每一个偶环，假设长度为 k，则只要 \dfrac{k}{2} 个人忘带，则都收不到。

  2. 对于每一个奇环，则只要 \dfrac{k+1}{2} 个人忘带，则都收不到。

所以我们可以用贪心的思想。

对于一个长度为 m 的环，只要 m 个人忘带，则就会有 m 个人收不到礼物。

如果能找到若干个环，使得它们长度之和刚好是 k，那么答案就是 k。否则会多牵连一个人，答案则为 k+1。