二分答案这四个字在我刚学算法的时候听上去像一个高深的技巧后来带过几轮新手之后发现它本质上就是把“猜数字”的游戏套在了一道算法题上。你不需要推导复杂的数学公式也不需要什么高深的图论知识只要你能写对一个判断函数就能用 O(logN) 次判断去逼近一个最优化问题的答案。这篇文章我想用两道最经典的题目——砍树和跳石头把二分答案的完整套路讲清楚。无论你是准备算法竞赛、考研机试还是面试刷题只要跟着这两道题走一遍后面再见到“最大值最小”“最小值最大”这类描述你第一反应就应该是二分答案。1. 为什么“二分答案”的本质是猜数字游戏最优化问题转判定问题1.1 二分法不是数据结构而是一种淘汰搜索空间的策略很多人一听到“二分”脑子里只有“在一个有序数组里找一个数”。这个印象不能说错但把二分的作用想窄了。二分真正厉害的地方是它对“搜索空间”做收敛只要你能确定一个单调变化的属性每次都能扔掉一半不可能的区域最后在 O(logN) 步内逼近目标。生活里我们其实每天都在用这个思路。你玩“猜数字”的时候如果告诉你答案在 1 到 100 之间每次猜完对方只能说“大了”或“小了”你很快就会从 50 开始猜。没有人会从 1 开始一个一个试因为那样太蠢了。二分答案就是把这种猜法搬到算法题里答案范围是连续的整数或实数每次取一个中间值去验证根据验证结果决定保留左边还是右边。1.2 把“求最优值”变成“判定可行性”普通二分的对象是数组元素二分答案的对象是一个“可能的答案”。比如题目要求“求一个最大高度 H使得能砍到至少 M 米的木材”如果你直接去构造这个 H会有点无从下手。但是反过来问给定一个高度 H你能不能算出砍下来的木材有多少这是很简单的。这就是“判定问题”。所以二分答案的核心转换是不直接去找最优解而是猜一个答案 x然后写一个 check(x) 函数回答“x 是否可行”。猜的次数是 O(log 值域)每次 check 的代价通常是 O(n) 或者 O(n logn)。所以总复杂度往往是 O(n logV)V 是答案的取值范围。这个复杂度在竞赛题里非常舒服。1.3 适用二分答案的两个硬性前提不是什么题都能二分答案硬凑只会引起混乱。一个好的二分答案题必须同时满足两点。第一答案本身是单调的。什么叫单调就是如果 x 可行那么比 x 更宽松的所有值也可行或者反过来如果 x 可行比 x 更严格的所有值也可行。比如砍树的高度 HH 越低砍下来的木材越多所以“能否满足 M 米”这个判断在 H 增大的方向上呈现出“可行到不可行”的单调变化。第二check 函数的代价是可接受的。二分次数只有几十次但每次 check 如果都要跑一个 O(n^2) 甚至指数级算法那整体就崩了。所以 check 函数一般写成贪心、递推、模拟、简单统计这类低成本逻辑。这也是为什么“二分答案 贪心”是一对黄金搭档二分负责枚举答案贪心负责在 O(n) 内判断答案是否可行。2. 第一题“砍树”最小化高度求最大收益的完整拆解2.1 题目背景树林里选锯片高度先看第一题洛谷 P1873砍树。题目给你 N 棵树的高度每棵树高度用正整数 a_i 表示。现在你要设置一个锯片高度 H然后用锯片水平扫过去凡是高度大于 H 的树就会被切掉高出 H 的那一部分也就是 total ∑ max(0, a_i - H)。你要保证切下来的木材总长度至少为 M 米同时希望 H 尽量大因为锯片越高工人越舒服树也越不容易被浪费。换句话说求最大的整数 H使得 ∑ max(0, a_i - H) ≥ M。我见过不少人直接排序后从下往上模拟或者试图找什么规律其实完全没必要。这个题是二分答案最标准的入门样例。2.2 单调性分析高度升高的方向可行性在下降我们假设存在一个 H0 可行也就是 ∑ max(0, a_i - H0) ≥ M。现在把 H 提高一点点变成 H1 H0。因为每棵树的贡献 max(0, a_i - H1) 只会比 max(0, a_i - H0) 小所以总和只会减少。也就是说如果 H0 可行那么所有比 H0 更小的 H 一定也可行相反如果 H0 不可行那所有更大的 H 都一定更不可行。这个单调性告诉我们一件事所有可行 H 落在数轴上的一段前缀里所有不可行 H 落在后缀里。我们要找的就是可行区间的右边界。这种“左可行右不可行”的结构正是二分答案最理想的狩猎场。2.3 check 函数写起来像开卷考试砍树的 check 函数特别直白。给定一个高度 h遍历所有树把每棵树的贡献加起来比 M 大就说明可行。bool check(int h, vectorint a, int m) { long long sum 0; for (int x : a) { if (x h) sum x - h; } return sum m; }注意这里 sum 要用 long long。树高最多 10^9树的数量最多 10^6最坏情况下每棵树都砍到接近 0总和很可能超过 int 的 2^31 范围。这个坑我第一次刷的时候踩过WA 到怀疑人生最后发现只是 int 溢出。2.4 二分区间怎么设计右端点一定要取到理论最大值二分高度 H 的区间左端点取 0右端点取 0 还是取所有树的最大高度初始我建议直接取 max(a_i)。为什么如果 H 大于树的最大高度那所有树贡献都是 0根本不可能满足 M 0 的情况。所以 H 的答案一定不会超过最大树高。取 0 作为左端点也合理因为 H0 时所有树全被砍掉理论上能获得最多木材只要 M 不大于树高总和H0 一定可行。于是整套主逻辑就出来了#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; vectorint a(n); int l 0, r 0; for (int i 0; i n; i) { cin a[i]; r max(r, a[i]); } auto check [](int h) { long long sum 0; for (int x : a) { if (x h) sum x - h; } return sum m; }; while (l r) { int mid (l r 1) / 2; // 关键向上取整 if (check(mid)) l mid; else r mid - 1; } cout l endl; return 0; }这里的 mid 为什么要写成 (l r 1) / 2而不是 (l r) / 2这是整数二分最典型的死循环陷阱。如果 l 和 r 相差 1比如 l5, r6那么 (lr)/2 5check(5) 如果是 truel mid 5区间没有缩小陷入死循环。向上取整之后 mid6则无论 check 结果如何区间都会缩小。这个细节在下面的章节里我还会重点讲。2.5 砍树这题的两个经典坑第一个坑是check 里面提前退出。如果你已经累积够了 M可以提前 break能省一点时间。但要注意不要因为提前退出而影响后续判断这里累加结果只跟“是否达到 M”有关所以提前退出是安全的。第二个坑是读入数组后直接排序会不会更好。排序不会改变答案但也没必要。check 函数不在乎树的顺序线性扫描一遍就够了。如果硬排序复杂度多一个 O(n logn)对于 10^6 的数据也不致命但没必要。我见过有人按树高排序后想着用二分优化 check其实就是画蛇添足。3. 第二题“跳石头”最小距离最大化的贪心判定设计3.1 看懂“最短跳跃距离最大化”第二题是 NOIP2015 的跳石头原题编号 P2678。一条河从起点 0 到终点 L河中间有 N 块石头每块石头到起点的距离是 d_i。选手要踩着石头从起点跳到终点。现在允许你移走最多 M 块石头不能移走起点和终点问移走之后选手在整个跳跃过程中任意一次跳跃的最短距离最大可能是多少。这句话有点绕。拆开看移走石头后跳跃路径由起点、若干块保留石头、终点组成。相邻两点之间的距离会有一个最小值我们把这个最小值称为“最短跳跃距离”。题目要你通过合理安排移走哪些石头让这个最小值尽可能大。这种“最小值的最大值”是二分答案的经典题设。如果题目要求你求“最大值的最小值”同样也是二分答案的信号。背后的原因就是当你设一个答案 mid 时判断 mid 是否可行往往比直接构造最优解容易得多。3.2 判定函数的贪心逻辑移走“碍事”的石头现在给定一个 mid我们要判断能不能通过移走不超过 M 块石头让所有相邻跳跃距离都至少为 mid。这个 check 可以这样想从起点出发不断往前找石头。如果当前石头离上一块保留石头太近距离小于 mid那这块石头就属于“碍事”的石头移走它否则就保留它并把它的位置作为新的“上一块保留石头”。最后统计一下移走了多少块如果 ≤ M说明 mid 可行。写成代码bool check(int mid) { int cnt 0; // 移走石头数量 int last 0; // 上一个保留石头的位置0 是起点 for (int i 1; i n; i) { if (d[i] - last mid) { cnt; // 这块石头离得太近移走 } else { last d[i]; // 保留这块石头 } } // 单独处理终点如果最后一个保留点到终点距离不足 // 说明这个方案下没有合法跳跃直接返回 false if (L - last mid) return false; return cnt m; }等一下我上面这种写法对开头举的反例会误判吗我们验证一下L10n2d[1]5d[2]9m1mid4。last0i15-05 ≥ 4保留 last5i29-54 ≥ 4保留 last9最后 L-last1 4返回 false。但实际上移走 9 后路径为 0 - 5 - 10最短距离 5mid4 是可行的。所以这个写法是错的这暴露了一个隐藏逻辑当终点距离不足时我们需要考虑的不是简单返回 false而是回头去看看最后那一段附近是否可以通过多移走一块石头来满足。经典的 AC 写法其实是把终点也放进循环并且终点距离不足时也把 cnt 加一。为什么这样反而正确因为它在贪心求“最少要移走多少块石头”时把终点当作一个不能保留的障碍物来计数这个计数值恰好等于最少需要移走的石头数。很多题解直接用这种写法但不解释原理容易让新手困惑。我这里给出 NOIP 标准写法bool check(int mid) { int cnt 0; int last 0; for (int i 1; i n 1; i) { int cur (i n 1 ? L : d[i]); if (cur - last mid) { cnt; } else { last cur; } } return cnt m; }在这个写法里当终点 curL 与 last 的距离不足时cnt 会加一代表必须对最后一个区间再做一次“移除石头”的操作。这个操作不是真的移走终点而是等价于把之前某一批相邻石头合并处理最终得到的 cnt 就是满足“每段距离都不小于 mid”所需的最少移除数量。第一次看到这个写法的人都会觉得别扭但你只要记住这是经过验证的贪心写法终点视为不可移除但计数的效果等价于正确的最小移除数。等你多刷几道类似题会发现很多 check 函数都长这样。3.3 二分边界与完整代码跳石头的答案范围在 1 到 L 之间。左端点可以取 1右端点取 L。因为最短跳跃距离不可能小于 1坐标都是整数不可能超过总长 L。求的是“最大值”所以二分模板和砍树一样使用向上取整满足 check 时向左半区收缩不对我们想求最大的可行 mid。当 check(mid) 为 true说明 mid 可行但可能还有更大的答案所以 l midcheck(mid) 为 false说明 mid 太大需要缩小所以 r mid - 1。因此使用 l mid 的模板mid 要向上取整。完整代码如下#include bits/stdc.h using namespace std; int L, n, m; int d[50005]; bool check(int mid) { int cnt 0; int last 0; for (int i 1; i n 1; i) { int cur (i n 1 ? L : d[i]); if (cur - last mid) { cnt; } else { last cur; } } return cnt m; } int main() { cin L n m; for (int i 1; i n; i) cin d[i]; int l 1, r L; while (l r) { int mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; } cout l endl; return 0; }这个例子里的 check 已经不是简单累加了而是用贪心模拟了“每块石头是否移除”的过程。跳石头所以进阶是因为它教了你二分答案 贪心判定是一个极其好用的组合。3.4 为什么这题不能直接贪心求答案而必须二分有人会想既然 check 里用了贪心能不能直接贪心一次算出最大最短距离呢不行。原因很简单答案是“最短距离的最大值”这个值不是一个具体的石头位置而是一个距离尺度。你很难一次遍历就确定这个尺度。但如果你把距离作为一个参数传进去贪心就可以告诉你“给定这个距离能不能做到”。这就像你要找一个锁的密码直接猜密码很难但给你一个密码让你试一下能不能开锁很容易。二分答案提供了系统的猜法贪心当了那个试锁器。两者分工明确。4. 两道题的共同骨架一份可套用的整数二分模板与识别信号4.1 二分答案题的“信号词”很多读者刷题时会迷茫什么时候该用二分答案我根据自己的经验总结了几个高频信号。题面出现“最大值最小”或“最小值最大”题面出现“求最大可能值/最小可能值”而且答案是一个单调的量题目里有一个明显的“试着猜一个答案然后验证”的过程数据范围很大但 check 可以写成 O(n) 或 O(n logn)砍树属于“求最大高度使得获得木材量不少于 M 米”跳石头属于“求最大的最短距离使得移走石头数不超过 M”。它们都符合“答案单调”和“check 可快速模拟”这两个条件。4.2 整数二分模板记住两个方向就够了网上关于二分的模板五花八门但本质只有两个方向第一种求“满足条件的最小值”时while (l r) { int mid (l r) / 2; if (check(mid)) r mid; // 可行向左边找更小 else l mid 1; // 不可行向右边找 }第二种求“满足条件的最大值”时while (l r) { int mid (l r 1) / 2; // 注意向上取整 if (check(mid)) l mid; // 可行向右边找更大 else r mid - 1; // 不可行向左边找 }砍树和跳石头都属于第二种。千万不要死记硬背你要记的是当 check(mid) 为 true 时答案应该保留哪半边如果是求最大值true 说明 mid 可行那么区间左边界可以收缩到 mid如果是求最小值true 说明 mid 可行那么区间右边界可以收缩到 mid。想一想就不会选错。4.3 区间初始值怎么定从题目逻辑出发初始区间的左端点和右端点建议不要拍脑袋写 0 或 INF而是根据题目含义推。砍树答案 H 最小可以为 0最大不可能超过最高树所以 l 0, r max(a[i])。跳石头最短距离最小可以取 1最大不可能超过总长 L所以 l 1, r L。如果你把右端点设成 1e9 之类的极大值也不是不行但会浪费几次二分而且如果 check 里没有对极大值做好边界处理容易出现溢出或逻辑错误。我建议把区间收窄到题目允许的理论范围既清楚又安全。4.4 一个常见的“最小答案”例子如果题目变成求最小可行值如果你理解了上面两个模板那么“最大值”“最小值”的题目都能应付。比如把砍树改成“求一个最小的 H使得砍掉的木材量不超过 M”这时候可行区间就从“可行前缀”变成“不可行前缀”check 不变但二分方向要反过来。练题时最好把两个方向都写一遍不要只满足于会做这两道题。5. 写二分答案最容易翻车的四个地方从死循环到check函数5.1 死循环的根源mid 取整方向与区间更新不匹配我在带新手的时候几乎每个人都在整数二分上写过死循环。最典型的问题出现在求最大值模板里。如果你用了mid (l r) / 2同时更新规则是l mid当 l5, r6 时mid5check(5) 为 true下一轮 l 还是 5r 还是 6无限循环。解决方式永远只有一个如果你在分支中写了 l mid就必须让 mid 向上取整。反过来如果你写了 r mid那么 mid 向下取整没问题但如果你写了 l mid 1向下取整也没问题。你可以把这两条规则写在代码注释里每次写之前先念一遍。5.2 区间端点没有覆盖到答案第二个常见问题是右端点定小了。比如砍树如果右端点取成中间的某棵树高答案可能正好大于该值吗不可能因为锯片高度超过所有树高时木材为零但如果 M 为 0 呢有些题 M 可能是 0这时答案应该取最大树高甚至更大。通常题目会保证 M 0但最好先看清题面。跳石头的答案也不可能超过 L因为起点到终点的总距离就是 L最短跳跃距离不可能比 L 大。还有一种情况是左端点取 1但答案可能是 0。如果存在无论如何都满足不了最小距离为 1 的情况那应该输出 0 吗需要根据题意判断。很多二分答案题的输出最小是 0不能默认 l1。做题时先看样例和特殊数据别老觉得左边界一定是 0 或 1。5.3 check 函数里的数据范围和溢出砍树的 check 里求和可能超过 int跳石头的距离相减也可能涉及大数。我强烈建议所有跟累加、乘法有关的地方都使用 long long。尤其是当题目给的树高、距离范围达到 10^9 时int 很容易被击穿。刷题时看到“10^9”“10^18”这类数字第一反应就是开 long long。5.4 浮点数二分两个题之后的延伸如果你要做浮点数二分模板会变成 while (r - l eps)eps 根据题目精度要求设 1e-6 或 1e-7。这时候不再有死循环问题但要注意的是浮点数比较不能直接用 以及输出时保留的小数位数。浮点数二分本质上和整数二分一样只是终止条件不同。练完这两个题你完全可以自己改一个浮点版试试比如求正多边形内切圆半径这类题。5.5 为什么我认为练这两个题就能掌握二分答案砍树教给你二分答案的基本框架单调性分析、check 函数、区间初始化。跳石头在此基础上加上了贪心判定让你明白“答案不可直接求但可以通过判定去逼近”。这两个题正好覆盖了二分答案最重要的两种形态直接判断可行性的简单 check和需要贪心模拟的复杂 check。我在带训练时经常跟学员说不是刷的题越多越好而是要把一道题吃到消化为止。这两个题如果每个都能独立写三遍第一遍默写第二遍关掉题解边想边写第三遍尝试改成求最小值的模板那么你对二分答案的理解会比刷十道类似题还扎实。后面再遇到“最大化最小值”的题目你最大的困难往往不是二分答案本身而是如何设计那个贪心 check 函数了。我个人写二分答案时还有一个习惯每次二分之前先手动模拟一组很小的数据确保 check 函数能在纸上画出过程。这个习惯帮我避开了很多麻烦。只要你也能耐下心做这一遍模拟二分答案这道门槛就真的被迈过去了。