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

砍树

题目描述

链接：砍树 (Luogu P1873)

解题思路

设伐木机的高度为 H，能得到的木材总量为 C。根据题意可以发现明显的单调性质：

• 当 H 增大时，C 减小。
• 当 H 减小时，C 增大。

我们要找的是满足 C >= M 的最大高度 ret。这同样符合二段性：

• 当 H <= ret 时，C >= M。
• 当 H > ret 时，C < M。

因此，我们可以对高度 H 进行二分。判定函数中，对于每棵树，如果树高超过 H，则累加差值作为木材量。

代码实现

#include <iostream>
using namespace std;

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

LL a[N], n, m;

// 计算高度为 mid 时能得到的木材量
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];

    // 二分查找最大高度
    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 的计算方式，避免死循环或越界。