试着写了一个不用二分的题解,然而死活想不出为什么2,3,5,6,9,10号测试点会失败
#include <bits/stdc++.h>
using namespace std;
int N, H, a[1000005]={}, b[400005]={};
long long M;
int main() {
long long sum=0;
cin >>N >>M;
for (int i=1; i<=N; i++) {
cin >> a[i];
sum += a[i]; //计算所有树的高度和
b[a[i]] += 1; //记录每个高度对应的树的数量
}
for (int i=1; sum>=M && i<=400000; i++) {
H=i;
sum = sum - N; //锯片每调高一米,砍下的总木材减少N
N = N - b[H]; //当前与锯片同高的树,下一次不会被砍到
}
cout << H-1 << endl;
}