问题标题: 酷町堂：5549 伐树（cut）

5549   伐树（cut）

经验值：1600 时间限制：500毫秒 内存限制：128MB

庐阳区2020年信息学竞赛试题

 不许抄袭，一旦发现，直接清空经验！

题目描述 Description

李老板需要总长为M米的木材，他安排光头强去砍树。树林里有N棵树，为了保护环境，不能将一个树完全砍掉，会留出一部分， 因为这样树还可以继续生长。光头强将他的砍树装置的锯片高度设置为H米，这样可以锯掉所有的树比H高的部分。求在得到M米木材的前提下，H的最大值。
比如，一共有4棵树，高度分别为20、15、 8、17. 需要6米的木材，若将锯片的高度设置为15米，这样可以得到的木材为5+0+0+2=7米， 若锯片的高度提高1米，设置为16米， 只能得到木材的长度为4+1=5。为了得到6米的木材，锯片的高度最大只能设置为15米。

输入描述 Input Description

第一行两个整数N和M。
第二行，N个整数，表示每棵树的高度。

输出描述 Output Description

一个整数，意义如题所述。

样例输入 Sample Input

4 6 20 15 8 17

样例输出 Sample Output

15

数据范围及提示 Data Size & Hint

对于30%的数据，
树的高度不超过100米，1<=N<=100
对于50%的数据，
树的高度不超过1000米，1<=N<=1000
对于100%的数据，
树的高度不超过100000米，1<=N<=100000，1<=M<231
保证N棵树的总长度不小于M

#include<bits/stdc++.h>
using namespace std;
int a[100011],maxa;
long long n,m;
long long check(int k){
    long long cnt=0;
    for(int i=1;i<=n;i++) cnt+=max(a[i]-k,0);
    return cnt>=m;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        maxa=max(maxa,a[i]);
    }
    int l=1,r=0x3f3f3f3f;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d",l);
    return 0;
}

超时40分。

怎么改？？？？？？

怎么改？？？？？？

怎么改？？？？？？

怎么改？？？？？？

怎么改？？？？？？

怎么改？？？？？？

怎么改？？？？？？