A20952砍树——题解

首先要明确这道题是用二分的 ( 因为有标签 )：
有单调性

提高伐木机的高度，显然地，得到的木头会减少。

同样地，放低得到的木头会增多。

而正因为答案有单调性，所以我们可以使用二分。

数据范围大

显然，1e6 的 n 和 1e9 的数据量对于暴力枚举是不太友好的

穷举的话，复杂度大概是 $O(n·m)$ 绝对应该会超

然鹅二分就不会了，二分答案只要 $O(n·log m)$ 应该是不会超的qwq

#include<bits/stdc++.h>
using namespace std;
long long a[1000005];
long long zg,l,r,mid;
long long n,m;
bool ef(int x){
	long long sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]>x){
			sum+=(a[i]-x);
		}
	}
	return sum>=m;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		zg=max(zg,a[i]);
	}
	l=0-1;
	r=zg+1;
	while(l+1<r){
		mid=(l+r)/2;
		if(ef(mid)==1){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	cout<<l<<endl;
	return 0;
}