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

2.2 砍树

题目描述

有 N 棵树，高度分别为 a[1]...a[N]。需要砍掉一部分树木，使得得到的木材总量至少为 M。求伐木机设定的最低切割高度 H。

算法原理

设伐木机的高度为 H，能得到的木材为 C。 • 当 H 增大的时候，C 在减小。 • 当 H 减小的时候，C 在增大。 整个解空间具有单调性。设最终结果是 ret： • 当 H ≤ ret 时，C ≥ M（能得到足够的木材）。 • 当 H > ret 时，C < M（木材不足）。 同样使用二分查找寻找满足条件的最大 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];
    
    // 二分边界：高度从 1 开始，最大可能为 2e9
    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;
}

三、总结

二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性。思路清晰、效率极高。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。注意处理整数溢出和边界条件，特别是 mid 的计算方式，这往往是调试时的坑点。