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

2.2 砍树

题目描述

链接：砍树

解题思路

设伐木机的高度为 H，能得到的木材为 C。根据题意，我们可以发现如下性质：

• 当 H 增大的时候，C 在减小。
• 当 H 减小的时候，C 在增大。

那么在整个解空间里面，设最终的结果是 ret，于是有：

• 当 H ≤ ret 时，C ≥ M，也就是「伐木机的高度」小于等于「最优高度」时，能得到的木材「大于等于」目标值 M。
• 当 H > ret 时，C < M，也就是「伐木机的高度」大于「最优高度」时，能得到的木材「小于」目标值 M。

同样利用单调性进行二分，寻找满足条件的最大高度。

代码实现

// EKO/ 砍树
#include <iostream>
using namespace std;

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

LL a[N], n, m;

LL cacl(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];
    
    // 注意数据范围，r 需要足够大
    LL l = 1, r = 2e9;
    while (l < r) {
        LL mid = (l + r + 1) / 2;
        if (cacl(mid) >= m) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

总结

二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性，思路清晰、效率极高。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。在实际编码中，注意数据类型溢出和边界条件处理，比如 mid 的计算方式以及 check 函数的返回值逻辑。