二分答案-模板

//第一步，明确满足条件的锯片答案是单调性的
//第二步，需要 根据题目条件将锯片高度拿来二分，根据二分判断结果更新区间

#include<iostream>
using namespace std;
const int M = 1e6+10;
int a[M],n,m;
int Max=0;
//二分答案，其实就是对check的不同定义 

//看高度为x时 ，能否锯出m米，即判断能否满足条件 
int check(int x){
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(a[i]>x){
			ans +=a[i]-x;//记录锯出来的木材 
		}
	}
	//看看此时锯出的总木材ans是否大于等于m
	if(ans>=m) {
		return 1;
	}else{
		return 0;
	}
	//装 bi写法 ：return ans>=m; 
}


int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>Max){
			Max = a[i];//这个就是找出范围的最高值 
		}
	}
	int l=0,r=Max,ans=0,mid;
	//其实还可以无脑找范围，直接设一个大值;让 r = 2e9(高度最大值) 
	
	//下面其实就是二分模板，只是把mid改成要求的高度去做check判断 
	while(l<=r){
		mid = (l+r)/2; 
		if(check(mid)){//check，锯片高度为mid时，能否锯出m米长的木材 
			l = mid + 1;
			ans = mid;
		}else{
			r = mid - 1;
		}
	}
	cout<<ans; 

	return 0;
}
//Tian