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

前言

二分答案是算法竞赛中极具技巧性的解法，核心在于将复杂求解转化为'二分 + 判定'。它专门解决「最大值最小」或「最小值最大」类问题。只要解空间具有单调性（二段性），就能通过二分快速锁定最优解。

一、二分答案原理

准确来说，这属于「二分答案 + 判断」。当解空间从小到大变化时，如果判定结果呈现「满足」到「不满足」的跳变，即可二分。我们不需要直接求出答案，而是验证某个猜测值是否可行。

二、经典例题实战

1. 木材加工

题目描述 给定 N 根原木，长度分别为 $a_1, a_2, …, a_N$。需要切成至少 K 段等长的木料，求每段的最大长度。

思路分析 假设切出的长度为 $x$，那么第 $i$ 根木头能切出 $⌊ a_i / x ⌋$ 段。总段数 $∑ ⌊ a_i / x ⌋$ 随 $x$ 增大而减小。这是一个典型的单调性问题。我们要找最大的 $x$，使得总段数 $≥ K$。

代码实现

#include <iostream>
using namespace std;

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

LL a[N], n, k;

// 计算在切割长度为 x 的情况下能切几段
LL calc(LL x) {
    LL cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += a[i] / x;
    }
    return cnt;
}

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

    // 二分范围：左边界 0，右边界最大可能长度 1e8
    int l = 0, r = 1e8;
    while (l < r) {
        // 向上取整，避免死循环
        LL mid = (l + r + 1) / 2;
        if (calc(mid) >= k) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << l << endl;
    return 0;
}

2. 砍树

题目描述 有 N 棵树，高度为 $a_i$。设定一个伐木机高度 $H$，高于 $H$ 的部分被砍下。求能获得至少 M 单位木材时的最大 $H$。

思路分析 设获得木材量为 $C$。当 $H$ 增大，$C$ 减小；当 $H$ 减小，$C$ 增大。同样具备单调性。若最终结果为 $ret$，则当 $H ≤ ret$ 时 $C ≥ M$，反之 $C < M$。

代码实现

#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;
}

总结

二分答案的关键是抓住解空间的二段性。通过二分缩小范围，用判断函数验证合法性。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。注意数据范围，防止溢出，选择合适的二分模板即可高效解决此类问题。