二分答案专题实战：木材加工与砍树问题解析

这道题是经典的伐木机高度设定问题。我们需要找到一个高度 $H$，使得高于 $H$ 的部分总和至少为 $M$，同时 $H$ 尽可能高。

思路分析 设伐木机高度为 $H$，得到的木材量为 $C$。

• 当 $H$ 增大时，$C$ 减小。
• 当 $H$ 减小时，$C$ 增大。 这同样符合二分判定的二段性。若当前高度 $H$ 能切出足够的木材，说明还能再抬高一点；否则必须降低高度。

代码实现 注意数据范围较大，数组大小和变量类型要匹配。

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
typedef long long LL;

LL a[N], n, m;

// 计算高度为 mid 时能获得的木材总量
LL calc(LL mid) {
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] - mid > 0) ret += a[i] - mid;
    }
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    LL l = 1, r = 2e9;
    while (l < r) {
        LL mid = (l + r + 1) / 2;
        if (calc(mid) >= m) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

这两道题虽然场景不同，但本质都是利用单调性进行二分搜索。在实际刷题中，识别出「解空间单调」这一特征，就能迅速套用二分答案模板。关键是写好判定函数 check 或 calc，确保逻辑严密，避免死循环。