二分答案的核心思路
说到二分查找，大家可能更熟悉它在有序数组里找元素。但今天我们要聊的是它的进阶用法——二分答案。
二分答案准确来说，应该叫做「二分答案 + 判断」。它专门用来处理那些直接求解最优解比较困难，但验证一个解是否合法相对容易的问题。这类题目通常带有「最大值最小」或者「最小值最大」的特征。
核心在于利用解空间的单调性。如果随着某个参数（比如切割长度、机器高度）的变化，判定结果呈现出明显的二段性（即满足条件的一段区间和不满足条件的一段区间），我们就可以在这个解空间上进行二分，快速逼近最优解。
经典例题实战
1. 木材加工
问题描述 给定 N 根原木，每根长度为 $a_i$。现在需要切出 K 段等长的木料，问这 K 段木料的最大长度是多少？
解题思路 假设我们想切的长度是 x，那么对于每一根原木 $a_i$，能切出的段数就是 $ ext{floor}(a_i / x)$。把所有原木能切出的段数加起来，如果总数大于等于 K，说明 x 这个长度是可行的，甚至可能还能切得更长；反之，如果总数不够 K，说明 x 太大了，需要减小。
这里有一个细节要注意：当 x=0 时会导致除零错误，所以二分的左边界 l 至少从 1 开始。不过为了代码统一，有时也会设 l=0，在 check 函数里特判一下，或者直接设 l=1 更稳妥。
代码实现
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N], n, k;
// 计算在切割长度为 x 的情况下能切几段
LL check(LL x) {
if (x == 0) return 0; // 防止除零
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];
// 二分范围：最小 1，最大 1e8（根据数据范围调整）
int l = 1, r = 1e8;
while (l < r) {
LL mid = (l + r + 1) / 2;
if (check(mid) >= k) l = mid; // 可行，尝试更大的长度
else r = mid - 1; // 不可行，缩小长度
}
cout << l << endl;
return 0;
}
2. 砍树
问题描述 有一片森林，每棵树的高度为 $a_i$。我们需要砍伐树木获得至少 M 长度的木材。伐木机设定一个高度 H，高于 H 的部分被砍下。求 H 的最小值。
解题思路 这个问题和木材加工非常像，只是目标变成了「最小化高度」。逻辑是一样的：
- 如果设定的高度 H 比较低，那么砍下来的木材总量 C 就会比较多。
- 如果设定的高度 H 比较高，那么砍下来的木材总量 C 就会比较少。
这种单调关系让我们可以二分 H。如果当前高度 H 砍下来的木材够 M，说明 H 还可以再高一点（这样更省树），于是 l = mid；如果不够，说明 H 太高了，得降下来，于是 r = mid - 1。
代码实现
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
LL a[N], n, m;
// 计算设定高度 mid 时能得到的木材量
LL check(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 (check(mid) >= m) l = mid; // 木材够了，尝试更高的高度
else r = mid - 1; // 木材不够，降低高度
}
cout << l << endl;
return 0;
}
总结
这两道题虽然背景不同，但本质都是利用二分答案将优化问题转化为判定问题。关键点在于确认解空间的单调性，并编写高效的 check 函数。时间复杂度通常是 $O(n imes ext{log}( ext{max_val}))$，对于大规模数据也能轻松应对。掌握这个模板，遇到类似的「最大化最小值」或「最小化最大值」问题，基本就能迎刃而解了。
