前言
二分答案（Binary Search on Answer）是算法竞赛中处理「最值」类问题的利器。它的核心思想是将求解最优解的问题，转化为判断某个值是否可行的问题。当解空间具有单调性时，我们可以通过二分快速逼近答案。
一、二分答案原理
准确来说，这叫做「二分答案 + 判定」。
如果解空间在变化过程中，判断结果呈现「二段性」（例如：小于等于某值都满足条件，大于都不满足），就可以二分这个解空间。这类问题通常表现为「最大值最小化」或「最小值最大化」。
二、经典例题实战
1. 木材加工
题目描述 给定 n 根原木，长度分别为 $a_1, a_2, \[dots], a_n$。要求切成 k 段等长的木条，求每段的最大长度。 （参考洛谷 P2440）
思路分析 我们要找的是最大的切割长度 $x$。 假设我们尝试切长度为 $mid$，如果能切出至少 $k$ 段，说明 $mid$ 可能偏小或者刚好，可以尝试更大的值；反之则说明 $mid$ 太大，需要减小。 这就是典型的单调性：长度越短，能切出的段数越多。
代码实现
// 木材加工
#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，下界设为 1
int l = 1, r = ;
(l < r) {
LL mid = (l + r + ) / ;
((mid) >= k) l = mid;
r = mid - ;
}
cout << l << endl;
;
}
