二分

我们发现，$H$ 在答案区间 $[1,\max(a_i)]$ 内得到的木材长度非严格单调递减。确定了答案的单调性，我们可以使用二分答案。时间复杂度为 $O(n\log n)$。

#include<iostream>
using namespace std;

int n,m,h,l,r,ans,a[1000005];
int main(){
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		cin >> a[i];
		h = max(h, a[i]);
	}
	l=0, r=h;
	while(l<=r){
		long long sum=0;
		int mid=(l+r)>>1;
		for(int i=1; i<=n; i++){
			sum += max(0, a[i]-mid);
		}
		if(sum>=m) ans=mid, l=mid+1;
		else r=mid-1;
	}
	cout << ans << endl;
	
    return 0; 
}