Description

有一个长度为 $n$ 的数列，每过一个单位时间所有数都减 $1$ ，一旦数列中有一个数变成 $0$ 就结束。有 $m$ 次给数列中的数加 $1$ 的机会，但一个单位时间只能选一个数加 $1$ ，问最多进行多少时间

Solution

本来一个单位时间能选多个数加 $1$ 的话就是一道经典题，直接二分答案即可
这题也是二分答案，但是每个单位时间只能加 $1$ 个数就让人很头疼
可以转化一下命题，改成：一个单位时间不能选多个数同时加 $1$
这样，就可以对于每个数，在它需要加 $1$ 的时候判断有没有其他数与其冲突
若所有数都不冲突，则满足条件

Code

二分答案部分

bool chk(int x){
	ll sum=0;
	for (int i=1;i<=n;i++) sum+=max(x-a[i],0);
	if (sum>m) return 0;
	for (int i=1;i<=n;i++)
		if (sum-max(x-a[i],0)>a[i]) return 0;
	return 1;
}