【二分+贪心】CF1665 C

Problem - C - Codeforces

题意：

思路：

一开始想太简单wa6了

只想到先感染大的分量，然后最后把最大的分量剩下的染色

但是可能会有别的分量更大（因为最后给最大的染色之后可能不再是最大的）

可以用堆维护，但是这里用二分做法

我们可以二分答案mid,问题就变成了mid秒内能否感染所有结点.

首先Injection一定用于优先感染兄弟结点比较多的结点,这样可以充分利用Spreading,我们可以结点按照兄弟的数量排序,然后优先感染兄弟多的结点.这样我们就知道了,第一秒被Injection的结点剩下的时间里可以被Spreading mid-1个兄弟,第二秒可以被Injection的结点可以被Spreading mid-2个兄弟,所以我们扫描一遍就可以知道还剩下多少个兄弟结点还没被感染,判断能否用剩下的Injection的操作将这些结点感染即可. 

Code：

#include <bits/stdc++.h>using i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 2e5 + 10;
constexpr int mod = 998244353;std::vector<int> adj[N];int len = 0;
int a[N], b[N];bool check(int mid) {int remain = 0;for (int i = 1, j = mid - 1; i <= len; i ++, j --) {remain += std::max(0,  b[i] - j);}return mid - len >= remain;
}
void solve() {int n;std::cin >> n;len = 1;for (int i = 1; i <= n; i ++) {adj[i].clear();b[i] = 0;}b[0] = 1;for (int i = 2; i <= n; i ++) {int x;std::cin >> x;adj[x].push_back(i);}for (int i = 1; i <= n; i ++) {if (adj[i].size()) {b[++len] = adj[i].size() - 1;}}std::sort(b + 1, b + 1 + len, std::greater<int>());int ans = 0;int l = 1, r = 1e9;while(l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;r = mid - 1;}else {l = mid + 1;}}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while(t --) {solve();}return 0;
}