给定一个
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;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)