C. Tree Infection

Problem - C - Codeforces

题意：

有一棵树，最开始都是健康的，每次可以感染任意一个节点和将已感染的节点的同父节点下一节点传染，问最小 *** 作数。

题解：

一开始没啥思路，后来补题才想明白的QwQ

首先将每个节点都去感染，不用传染，肯定是最劣解（有可能是唯一解）。

每一个父节点下的直接子节点看作一个集合，那么问题就变成了一个数组，每次感染一个数，每次被感染的数-1，问什么时候sum为0。

那么我们尽量考虑去多的传染。

首先每次感染的同时是可以传染的。

那么早感染的就可以传染更多值。

为了不浪费，需要把集合里的数排个序，然后一个一个往后感染，算 *** 作数即可。

Editorial好像是直接模拟的，一堆STL，看不懂。

看了一个大佬是二分写的，这里参考一下。

肯定是有二分性质的。

那么考虑每个数一个一个感染，然后用一个数组记录每个数在感染后面的数时能够传染的最大值（x-num：每次感染都假设传染了，判断合法性）。

在感染完了后，我们把剩下的 *** 作数用于感染已感染的数（使其减一），由于是判断合法性，只要合法即可，不用考虑最优，所以成立。

#include 
#define mod 1000000007
#define int long long
using namespace std;
int a[200005],b[200005],n;
inline bool check(int x)
{
	for(int i=1;i<=n;i++) b[i]=0;
	int now=0;
	for(int i=1;i<=x;i++)
		if(a[i]) b[i]=x-now,++now;
	if(now>x) return 0;
	int s=0;
	for(int i=1;i<=n;i++)
		if(a[i]&&a[i]>b[i]) s+=a[i]-b[i];
	if(s+now>x) return 0;
	return 1;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n+1;i++) a[i]=0;
		++a[1];
		for(int i=1;i> x;
			++a[x+1];
		}
		++n;
		sort(a+1,a+n+1);
		reverse(a+1,a+n+1);
		int l=0,r=n,ans=0;
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(check(mid)) ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout << ans << "\n";
	}
	return 0;
}

ps：补题一定要先看题呀