1

CF #781 (Div. 2), (C) Tree Infection - la-la-wanf

 2 years ago
source link: https://www.cnblogs.com/la-la-wanf/p/16137298.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

CF #781 (Div. 2), (C) Tree Infection

Problem - C - Codeforces











Example
input
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
output
4
4
2
3
4

n个点组成一个树, 1作为根节点, 输入第2~n个数的父节点序号, 问最少几次感染操作会使得整棵树全被感染, 每次两种感染操作都会进行1. 感染: 单独感染一个点  2.扩散: 如果某一父节点的孩子有感染的, 则在此父节点下的一个孩子也可以被感染

开始想的按孩子数多少从小到大排序, 依次操作 --> 不行, 因为若出现多个父节点的孩子数一样且很多的时候, 不可以挨个依次操作, 每个孩子堆 都得先感染一个使得操作2不被浪费

正解: 也是先按孩子数从小到大排序, 孩子数q[i]减去每个孩子堆只会先单独感染一个点到最后感染的个数, 即q[i]-i-2,  2=根节点1感染一次+i的孩子第一次感染, 最后放到堆里, 每次最大的取出, 最大的-1再压进去, 直到小于等于cnt

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<double,double> PII;
const int N = 2e5+10;
int mp[N], sum[N];

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n, times=1;
        cin>>n;
        for(int i = 0; i <= n; i ++) mp[i] = 0, sum[i] = 0;
        for(int i = 1; i < n; i ++)
        {
            int a;
            cin >> a;
            if(mp[a]==0)times++;
            mp[a]++;//i的孩子数
        }
        vector<int> q;
        for(int i = 1; i <= n; i ++)
            if(mp[i])
                q.push_back(mp[i]);
                
        sort(q.begin(), q.end());
        
        priority_queue<int> sum;
        for(int i = 0; i < q.size(); i ++)
            if(q[i]-1-i > 0)
                sum.push(q[i]-2-i);
        
        int cnt = 0;
        while(sum.size())
        {
            int tt = sum.top();
            sum.pop();
            if(tt>cnt)
            {
                sum.push(tt-1);
                cnt ++;
            }
            else
                break;
        }
        cout << times+cnt<<endl;
    }
    
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK