【二分+贪心】CF1665 C

比眉伴天荒 2024-03-23 21:45 28阅读 0赞

[Problem - C - Codeforces][]

题意：

![acbe9c1d054143bb8090042f525333b9.png][]

![557b7c068d8b49c88eb7ef200ed16417.png][]

思路：

一开始想太简单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;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1665/problem/C
[acbe9c1d054143bb8090042f525333b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/de5eaea399f74367a010301b6e257ce8.png
[557b7c068d8b49c88eb7ef200ed16417.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cb4b73deb1cb4d599e1b0319b32da6e8.png