Codeforces Round #781 (Div. 2)C
我之前没有看懂题目,我现在把我认为正确的题意描述出来
有一棵树,一开始都没有病毒什么的,但是我们需要把这一棵树里的所有节点变成有病毒的,而把节点变成有病毒的只有两个操作,而每一秒都可以进行(只要可以进行,第一次第一个操作不可以,没有兄弟节点感染)
操作1:一个节点的子节点带上病毒了,而这一个没有带上病毒(只要一个节点带有病毒,那么它的一个兄弟节点就可以获得这个病毒)
操作2:任意选择一个节点
我们需要的是把所有的节点得到病毒的最少时间
我的第一反应是把所有同一个父节点的节点发在一起,(把所有的兄弟都聚集在一起,统计每一个兄弟集合的数量)
我们可以有很多方式,但是有一个是一定的,那就是总时间t一定是大于等于进行操作一而得到病毒的数量
而且,只要有一个兄弟集合,就需要多少个操作二(把病毒引到这一个集合一定需要一个操作二才可以),其他的可以选择操作一,也可以选择操作二
然后我们知道如果一个r(操作数)可以让所有的子节点带上病毒,那么比r大的也一定可以,比r小的或许可以
那么这样,我们可以用二分的方式
具体操作可以看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include<map>
using namespace std;
const int maxn=1e5+10;
int t,n;
vector<int>f;
bool cmp(int x,int y)
{
return x>y;
}
bool check(int x) //x是总时间
{
if(x<f.size())return 0;
int sum=f.size();//sum是操作二的数量,一定要有集合个数个操作二(至少)
for(int i=0;i<f.size();i++)
{
sum+=max(0,f[i]-x+i);
//这个三角形是时间为7的最多子节点的情况,每一秒都会用到两个操作(第一秒只有一个操作,没有兄弟节点),这个是最优的形式,还有其他的样子,
// *(1) *(2) *(3) *(4) *(5) *(6) *(7) * * (多出的,比如这一次是7,那么这个多出的就一定
// *(2) *(3) *(4) *(5) *(6) *(7) 用到操作二,使用操作二,直接自己选择,而不
// *(3) *(4) *(5) *(6) *(7) 是通过兄弟节点
// *(4) *(5) *(6) *(7)
// *(5) *(6) *(7)
// *(6) *(7)
// *(7)
}
return sum<=x;
}
void solve()
{
cin>>n;
map<int,int>mp;
f.clear();
for (int i=1;i<n;i++)
{
int fa;
cin>>fa;
mp[fa]++;
}
mp[0]++;
for(auto [x,y]:mp)f.push_back(y);
int ans=n;
sort(f.rbegin(),f.rend());
// for (auto x:f)
// {
// cout<<x<<" ";
// }
// cout<<'\n';
int l=1,r=n;
while (l<=r)
{
int mid=(l+r)>>1;
if (check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
标签:781,int,Codeforces,mid,操作,Div,include,节点,病毒
From: https://www.cnblogs.com/righting/p/17020448.html