二分答案专题实战：木材加工与砍树问题详解
二分答案是算法竞赛与笔试中极具技巧性的高分解法，核心思路是将复杂求解转化为简洁的二分 + 判定。它专门解决「最大值最小」「最小值最大」等经典问题。如果解空间在从小到大的变化过程中，判断答案的结果出现二段性，此时我们就可以二分这个解空间，通过判断找出最优解。
一、木材加工
题目描述
给定 n 根原木，长度分别为 a[1]...a[n]。要求切割出 k 段长度相等的木料，求每段的最大可能长度。
解题思路
这道题是典型的二分答案模型。假设我们切出的长度为 x，那么对于每一根原木 a[i]，能切出的段数是 a[i] / x。总段数就是所有原木切出段数的和。如果总段数 >= k，说明长度 x 可行，可以尝试更大的长度；否则需要减小长度。
这里的关键在于单调性：随着 x 增大，能切出的总段数必然减少。因此存在一个临界点，满足二段性，适合二分查找。
代码实现
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N], n, k;
// 计算在切割长度为 x 的情况下能切几段
LL calc(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];
}
// 二分边界：左边界为 0（或 1），右边界设为足够大，如 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;
}
二、砍树
题目描述
给定 n 棵树的高度，使用伐木机进行砍伐。设定一个高度 H，高于 H 的部分被砍下。要求砍下的木材总量至少为 M，求 H 的最大值。
解题思路
设伐木机的高度为 H，能得到的木材量为 C。根据题意可以发现明显的单调性：
- 当 H 增大的时候，C 在减小。
- 当 H 减小的时候，C 在增大。
我们需要找到最大的 H，使得 C >= M。这与木材加工问题的逻辑完全一致，只是计算方式不同。对于每棵树 a[i]，如果 a[i] > H，则贡献 a[i] - H 的木材。
代码实现
#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;
}
总结
二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性。这两道题虽然场景不同，但本质都是利用单调性将最优化问题转化为可行性判断。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。在实际刷题中，注意处理边界条件（如除零、溢出）以及二分的上下界设置，就能稳稳地拿到分数。