P1873 砍树题解

题目传送门

#include 

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int a[N];
int n;
LL m;

bool check(int x) {
    LL sum = 0;
    //构建一个条件检查
    for (int i = n; i >= 1; 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];
    //排序
    sort(a + 1, a + 1 + n);

    //左端点
    int l = a[1], r = a[n];
    //注意:按位置查找 l=1,r=n; 按值查找 l=a[1],r=a[n]
    while (l < r) {
        int mid = l + r + 1 >> 1;//砍树的高度
        if (check(mid)) l = mid;//如果满足条件，那么继续向大的逼近试试
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}