【Codeforfes】1665C Tree Infection 题解

【Codeforfes】1665C Tree Infection 题解,第1张

题目大意

给定一个 n n n节点的树,并且认定 1 1 1号节点为根。

初始时,所有节点都是未感染状态,而我们的任务是感染这颗树。


每一秒中,我们依次执行以下两个 *** 作:

  • 如果一个节点 v v v的儿子节点中,至少有一个未感染,那么我们就可以至多再感染一个 v v v的儿子节点
  • 感染一个任意未被感染的节点

输出最少需要多长时间感染所有节点。

题目链接

思路

观察发现,在同一个点的儿子节点是相互联系的,而与其它点没有任何关系。

所以,把每个节点的儿子节点分为一组。

每一组都至少需要被感染一次,因为病毒会在被感染的组中每一秒都传染一个,所以为了使得所需时间最少,我们从数量最多的组开始感染。

每一组都感染完之后,若还有组没有被完全感染,那么我们就需要继续感染来加快进度。

而因为所有组都被感染了,每过一秒,感染数都会增加,所以我们不妨二分答案,设过 x x x秒后可以感染完,那么数量小于 x x x的组就不用感染了,我们有 x x x次机会去感染还没有被感染的节点。

最后不要忘了,根节点也需要单独感染一次,额外花了一秒钟时间。

代码
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxN = 2e5 + 7;

int T, n, son[maxN], cnt[maxN];

bool cmp(int x, int y)
{
    return x > y;
}

bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= cnt[0]; ++i) {
        if(cnt[i] > x)
            sum += cnt[i] - x;
        else
            break;
    }
    return sum <= x;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        memset(son, 0, sizeof son);
        cnt[0] = 0;
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) {
            int x; scanf("%d", &x);
            son[x]++;
        }
        sort(son + 1, son + 1 + n, cmp);
        int mt = 0;
        while(son[n] == 0)
            n--;
        for(int i = 1; i <= n; ++i) {
            ++mt;
            son[i] -= (n - i + 1);
            if(son[i] > 1)
                cnt[++cnt[0]] = son[i] - 1;
        }
        if(cnt[0] == 0) 
            printf("%d\n", mt + 1);
        else {
            sort(cnt + 1, cnt + 1 + cnt[0], cmp);
            int sum = 0;
            for(int i = 1; i <= cnt[0]; ++i)
                sum += cnt[i];
            int l = 1, r = sum;
            while(l < r) {
                int mid = (l + r) >> 1;
                if(check(mid))
                    r = mid;
                else
                    l = mid + 1;
            }
            printf("%d\n", l + mt + 1);
        }
    }
    return 0;   
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://www.outofmemory.cn/langs/662221.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-18
下一篇 2022-04-18

发表评论

登录后才能评论

评论列表(0条)

保存