算法
(贪心、多重背包) $O(n\log n)$
一个简单的想法是从 $i$ 到 $p[i]$ 连一条有向边。
可以发现 $n$ 个点、$n$ 条边,每个点的出度和入度都是 $1$。
因此最后这个图会变成若干个环。
- 如何最大化收不到礼物的人数?
对应一个偶环,假设长度为 $k$
那么只要有 $\frac{k}{2}$ 个人忘带礼物,$k$ 个人就全都收不到礼物。
对于一个奇环,假设长度为 $k$
那么需要有 $\frac{k + 1}{2}$ 个人忘带礼物,$k$ 个人就会都收不到礼物。
贪心即可。
- 如何最小化收不到礼物的人数?
如果有一个大小为 $m$ 的环,只要让这 $m$ 个人都忘带,就会有 $m$ 个人收不到礼物。
因此如果能找到若干个环,只要他们的长度之和刚好是 $k$,那么答案就是 $k$。
否则会有一个环不能被完全覆盖,还会牵连一个人,答案就是 $k + 1$。
问题变成了有 $m$ 个环,第 $i$ 个环长度为 $L[i]$,一共有 $C[i]$ 个环。
能否凑出长度之和为 $k$ 的方案。
多重背包!
用二进制分组,拆成 $\log (C[i])$ 个物品,做 $01$ 背包。
时间复杂度:$O(n\log n)$
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
const int N = 1e6 + 10;
int a[N], cir[N];
int vis[N];
int L[N], C[N], V[N], f[N];
// 统计环的大小
int dfs(int u, int start, int len) {
if (start == u) return len;
else {
vis[u] = 1;
dfs(a[u], start, len + 1);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) cir[++cnt] = dfs(a[i], i, 1);
std::sort(cir + 1, cir + cnt + 1);
int kk = k, maxans = 0, t = 0;
for (int i = 1; i <= cnt; ++i) {
if (cir[i] / 2 <= kk) {
kk -= cir[i] / 2;
maxans += cir[i] / 2 * 2;
}
else {
maxans += kk * 2;
kk = 0;
}
if (cir[i] & 1) t++;
}
maxans += min(kk, t);
int tot = 0;
for (int i = 1; i <= cnt; ++i) {
if (cir[i] == cir[i - 1]) C[tot]++;
else C[++tot]++, L[tot] = cir[i];
}
cnt = 0;
for (int i = 1; i <= tot; ++i) {
for (int j = 1; C[i] > 0; j <<= 1) {
int t = min(C[i], j);
V[++cnt] = t * L[i];
C[i] -= j;
}
}
f[0] = 1;
for (int i = 1; i <= cnt; ++i)
for (int j = k; j >= V[i]; --j)
f[j] |= f[j - V[i]];
int minans = k;
if (!f[k]) minans++;
cout << minans << " " << maxans << '\n';
return 0;
}