python/TangDou/XiTi/1309.cpp

#include <bits/stdc++.h>

using namespace std;

int n, m, ans;
int a[1000006];

//如果从k开始为高度进行锯树，那么是不是可以满足大于m的要求
bool work(int k) {
    long long d = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] > k) d += a[i] - k;
    if (d >= m) return true;
    else return false;
}


int main() {
    //输入+输出重定向
    freopen("../1309.txt", "r", stdin);

    // n表示树木的数量，m表示需要的木材总长度
    scanf("%d%d", &n, &m);

    //l:树的最小值 r:树的最大值
    int l = INT32_MAX, r = INT32_MIN;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        //取得树的最大值
        if (a[i] > r) r = a[i];
        //取得树的最小值
        if (a[i] < l) l = a[i];
    }
    //这次二分不是对数组的二分，而是对值的二分
    while (l <= r) {
        //二分点
        int mid = (l + r) / 2;
        //如果这个数可以满足大于m的要求
        if (work(mid)) {
            //记录当前值，但不一定是最优解，需要继续探测，缩小范围，直到l和r相遇，最终ans里保存的就是结果
            ans = mid;
            l = mid + 1;
        } else { // 在大的这一半都不行，那么在小的一半中折半查找
            r = mid - 1;
        }
    }
    //输出结果
    printf("%d", ans);

    //关闭文件
    fclose(stdin);
    return 0;
}