前言
二分答案是算法竞赛与笔试中极具技巧性的高分解法，核心思路是将复杂求解转化为简洁的二分 + 判定，专门解决「最大值最小」「最小值最大」等经典问题。本文从原理到实战，结合两道高频例题，带你从零掌握二分答案的核心逻辑与代码模板。
一、二分答案核心逻辑
准确来说，这应该叫做「二分答案 + 判断」。二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从小到大的「变化」过程中，「判断」答案的结果出现「二段性」，此时我们就可以「二分」这个「解空间」，通过「判断」，找出最优解。
简单来说，就是先猜一个答案，然后验证这个答案是否合法。如果合法，尝试更大的；如果不合法，尝试更小的。关键在于找到那个单调变化的性质。
二、经典例题实战
1. 木材加工
题目描述
给定 n 根原木，长度分别为 a[1], a[2], ..., a[n]。现在需要切割出 k 段长度为 x 的木条。问 x 最大能是多少？
解题思路
这道题是典型的「最大化最小值」问题。如果我们切得越短，能得到的段数就越多；切得越长，段数就越少。这种单调性正是二分查找的基础。
我们可以二分枚举切割长度 x。对于每一个 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) {
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];
// 二分查找最大长度
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 棵树的高度，需要砍伐得到至少 m 长度的木材。设伐木机高度为 H，高于 H 的部分被砍下。求 H 的最大值。
解题思路
设伐木机的高度为 H，能得到的木材为 C。根据题意，我们可以发现如下性质：
- 当 H 增大的时候，C 在减小。
- 当 H 减小的时候，C 在增大。
那么在整个「解空间」里面，设最终的结果是 ret，于是有：
- 当 H ≤ ret 时，C ≥ M，也就是「伐木机的高度」小于等于「最优高度」时，能得到的木材「大于等于」M。
- 当 H > ret 时，C < M，也就是「伐木机的高度」大于「最优高度」时，能得到的木材「小于」M。
同样利用单调性进行二分。注意这里求的是满足条件的最大 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];
// 二分查找最大高度
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;
}
总结
二分答案的关键，是抓住解空间的二段性，通过二分缩小范围、用判断函数验证合法性，思路清晰、效率极高。掌握这一思维，不仅能拿下算法题，更能学会用逻辑拆解难题。前路漫漫亦有收获，坚持刷题、稳步进阶，你付出的每一份努力，都在为更优秀的自己铺路。
