二分答案是我在带新人刷题时最常被问到的一个知识点。很多人背熟了二分模板但拿到题还是不知道往哪儿套还有人把二分答案和二分查找混为一谈总觉得数组已经有序才能二分结果遇到求最大值最小问题直接蒙圈。我通常的解决办法很简单让新人先吃透两道题一道是经典的砍树题一道是经典的跳石头题。这两道题涵盖了二分答案最常见的两种设计思路也踩遍了这个技巧最容易出错的几个坑。这篇文章就来详细拆解这两道题从暴力推导到最终代码把二分答案为什么能成立、判定函数怎么设计、边界怎么处理一次说清楚。1. 先别急着写二分答案可验证、单调可分才是二分答案的地基1.1 普通二分是在数组里找数二分答案是在值域里猜测答案二分查找的目标是一个有序数组我们要在其中定位某个目标值的中位数比如在[1, 3, 5, 7, 9]里找 7。它的核心依赖是数组元素按大小排列所以每次比较都能排除一半。二分答案则完全不同。它面对的问题通常是答案是一个数值这个数值很难直接算出来但我能轻松验证某个值“能不能行”。比如“砍树”问题直接算最大锯片高度很复杂但给我一个高度 h我却能快速算出能砍到多少木材——验证比求解简单得多。既然直接求答案困难那就干脆在答案可能的数值范围里猜取中间值验证一下可行不可行根据结果缩小范围。很多人问普通二分要求数组有序二分答案要求的“有序”在哪里答案是在值域上。二分答案的答案范围一定是一个连续区间[low, high]并且“答案是否可行”这件事在这个区间上具有单调性——要么从“可行”逐渐变成“不可行”要么反过来。这种单调性才是二分答案能工作的根基。举个例子假设锯片高度为 h能得到的木材总量为 f(h)。h 越大能砍的木材越少所以“f(h) 是否大于等于目标木材量 M”这件事在 h 增大的过程中是一个从真到假的单调变化。正因为这个单调性我们才能放心地根据 mid 的可行性决定往左还是往右缩小区间。1.2 判定函数为什么总是比直接求解轻松先建立一个观念二分答案的核心工作量 90% 在 check 函数上二分框架本身只是表皮。为什么验证一个答案总是比直接求解容易我总结了一个非常本质的原因直接求解需要你考虑“最优的那个值到底是多少”往往要你把所有情况都算一遍或者要理解一个非常全局的最优结构。验证一个给定的值 mid你只需要回答“是否存在一种合法方案让答案达到 mid 或以上”。这是从“找最优”降级成“找可行”难度完全是两个等级。以跳石头题为例要求“移走若干块石头后最短跳跃距离的最大值”。这个最大值是什么直接求非常抽象。但反过来如果给你一个距离 mid问“能不能通过移走不超过 m 块石头让每一跳都至少是 mid”这个问题就变成了一次简单的贪心模拟——从左往右扫石头不满足距离就移掉。这就是验证的威力它把“全局最优”转化成了“局部判断”。二分答案的整个思想本质上就是用一个简单的 check 函数不断试探把“求最优解”这个难题改写成一连串“判断可行性”的简单问题。判定函数写多了你会发现它通常就是那几板斧贪心模拟、前缀和、计数、简单的 DP。不管哪种都一定比原问题的求解轻松得多。1.3 模板落地最大化可行答案和最小化可行答案的两种写法二分答案通常有两种方向新手最常在这里搞反。我先给出两个可直接抄的模板方向问题放在后面章节详细解释。场景一最大化可行答案。也就是“答案越大条件越苛刻越难满足”。我们要找的是满足条件的最大值。比如砍树h 越大能砍到的木材越少越难满足“砍够 M 米”的条件。方向是如果 mid 可行说明答案还可以更大往右搜如果 mid 不可行说明答案必须更小往左搜。int l 0, r maxPossible, ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; // mid 可行记录答案尝试更大 l mid 1; } else { r mid - 1; // mid 不可行必须降低要求 } }场景二最小化可行答案。答案越小条件越苛刻。我们要找满足条件的最小值。比如“要凑够某个量最少要多少钱”这类问题。方向是如果 mid 可行说明答案可以更小往左搜如果 mid 不可行说明答案必须更大往右搜。int l 0, r maxPossible, ans maxPossible; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; // mid 可行尝试更小 r mid - 1; } else { l mid 1; // mid 不可行必须增大 } }注意两个模板的ans更新位置完全不同。记一个简单的口诀可行就朝你要的方向缩但要先把当前这个可行值存下来。下面两节我们就拿两道具体题目把这两个模板的来龙去脉拆开看。2. 第一题砍树——把暴力枚举改成二分顺便治一治你的 long long 健忘症2.1 题目描述与暴力思路为什么暴力一定超时砍树是中国 OJ 上非常经典的入门二分题目洛谷编号 P1873英文版叫 EKO。题目大意是这样的有 N 棵树每棵树高度是a[i]。你要定一个锯片高度 h锯片会横扫每一棵树凡是高于 h 的部分都会被砍下来所以第 i 棵树能得到的木材量是max(0, a[i] - h)。现在你需要至少 M 米木材求满足条件的最大 h。为什么这题是最佳二分入门题因为它的单调性太明显了h 越大每棵树得到的木材越少总木材量单调递减。因此“总木材量 ≥ M”这件事随着 h 增大从 True 逐渐变成 False。我们要找的就是这个 True 区间的最右端点——也就是满足条件的最大的 h。先看暴力怎么做从 h 0 开始一路枚举到最高的那棵树每次把所有树都扫一遍算总木材量。假设最高树高度是H_max复杂度就是O(N * H_max)。N 轻松到 10 的 5 次方H_max 能到 10 的 9 次方这个量级跑一辈子也跑不完。二分答案能把这个复杂度降到O(N * log(H_max))log 一下之后大概跑 30 次左右完全不在话下。2.2 从枚举答案到二分答案单调性体现在哪暴力的思路是“从小到大挨个试 h”而二分的思路是“在值域上跳跃着试”。区别本质是暴力试完 h1 之后试 h2而二分直接试 hH_max/2然后根据结果把另一半全部排除。为什么能排除一半仔细看单调性h 增加时总木材量sum(max(0, a[i] - h))单调非增。假如我们试的 mid 已经能满足“总木材量 ≥ M”那么所有比 mid 小的 h 也一定满足因为更低的锯片能砍到更多木材。这些值全都不可能是答案因为我们要的是“最大 h”既然更大的还在右边那左边至少不优。反之如果 mid 不可行所有比 mid 大的 h 也一定不可行锯片更高只会砍得更少所以右边整个区间直接废弃。你看到了吗我们只需要一次判断就能排除一半的答案区间。这正是二分答案效率的来源每次验证只需要 O(N) 的时间但可以让搜索范围减半。至于搜索范围左端点可以设 0锯片高度为 0 表示把所有树都砍倒右端点设成最高的那棵树的高度即可——再高就没木材了不可能满足条件。2.3 完整实现和两个容易踩的坑下面给出砍树题的完整 C 实现。这里我故意保留了一些细节方便把坑讲清楚。#include bits/stdc.h using namespace std; long long n, m; long long a[1000005]; bool check(long long h) { long long sum 0; for (int i 1; i n; i) { if (a[i] h) sum a[i] - h; } return sum m; } int main() { cin n m; long long maxH 0; for (int i 1; i n; i) { cin a[i]; maxH max(maxH, a[i]); } long long l 0, r maxH, ans 0; while (l r) { long long mid (l r) / 2; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl; return 0; }第一个坑不开 long long一定给你颜色看。M 和树高的范围通常是 10 的 9 次方量级N 是 10 的 5 次方量级sum的总量级轻易到 10 的 14 次方。这个数 int 完全装不下l、r、mid、a[i] 全套 long long 才是稳妥的。我用 int 写过一次结果在本地测试数据小没事一交上去答案全是负数调试了半天才发现是溢出。第二个坑ans 初始化与更新时机。如果你的 check 成立时只是把l mid 1而没有单独记录ans mid最后输出的可能是一个“已经不可行但恰好跳过去”的值。在二分答案中“最后一次可行的位置”和“搜索结束后的 l/r”不一定是同一个值必须用 ans 变量显式存下来。我见过有人直接用cout l - 1这本质上依赖了模板特性虽然能过但逻辑上不如显式存 ans 清楚而且一旦把边界条件改一改就很容易出 bug。这个题目很简单但它是理解二分答案方向的最佳窗口check(mid) 为真答案在右侧check(mid) 为假答案在左侧。把这道题独立手写三遍第一题的功力就算到位了。3. 第二题跳石头——贪心验证和二分边界一个是思路一个是体力活3.1 题目到底在问什么最大化的最小值理解跳石头是 NOIP 2015 提高组的经典题洛谷编号 P2678也是二分答案的第二块敲门砖。题目描述如下一条河道长度为 L起点在 0终点在 L中间有 N 块石头每块石头的位置是d[i]且递增。现在你要移走 M 块石头只能移中间的起点和终点不能动使得选手从起点跳到终点时每一跳的距离最小值尽可能大。直白点说移掉几块石头后剩下的石头把河道分成了若干段其中最短的一段就是我们说的“最短跳跃距离”。我们要通过选择性地移走石头让这个最短距离尽量长。这类问题有一个非常响亮的标签最大化最小值。与之对称的是最小化最大值。这两种描述几乎是二分答案的代名词。为什么因为“最小值的最大值”很难直接求但它天然适合二分如果我问你“最短跳跃距离能不能达到 5”你只需要模拟一下移石头的过程非常直观而直接问“最小距离最大能是多少”你根本无从下手。3.2 判定函数里的贪心模拟跳的过程核心是 find/mid 的判定函数检查能否通过最多移走 M 块石头让每一跳的距离都至少是 mid。做法非常朴素从起点开始从左到右扫每一块石头维护一个last表示上一块没有被移走的石头位置。对于当前石头d[i]计算它和last的距离如果d[i] - last mid说明这一跳太短必须处理。怎么处理移走当前这块石头cntlast保持不变。如果d[i] - last mid这一跳合格那么当前石头应当保留更新last d[i]。最后检查cnt M是否成立成立说明 mid 可行否则不可行。这里有个常见疑问为什么距离太短的时候移走的是当前石头而不是上一块核心原因是移动当前石头不影响已经确定的前面部分。假设last之前的部分已经全部满足了距离要求现在当前石头离last太近如果移走last那last之前的石头到后面石头的距离会变得更远但可能破坏last与更前面石头的间距。简单说前面的布局已经定了不要动它动当前这块代价最小且对未来影响可控。这是贪心成立的关键推理在面试或讲题时一定要能说出来。严格来说这种贪心的正确性需要证明如果存在一种合法方案那么“从左到右遇到不合格就移掉当前石头”的方案移走的石头数量一定不会更多。证明思路就是交换论证这里不展开但你可以放心使用。3.3 边界处理细节终点、起点、移走几块跳石头题的边界问题比砍树多得多我把容易踩的地方集中列一下。起点和终点不能移。我们的贪心过程从起点开始last初始化为 0这没问题。但终点 L 是一块“特殊石头”它不能出现在“移走”的列表里。怎么处理两种常见做法我推荐第二种。做法一把终点当作第 N1 块石头d[N1] L在扫的时候把它也纳入判断。如果终点那一跳不合格不能移终点那怎么办逻辑上相当于把上一块保留的石头移走让更靠前的石头去接终点所以cnt后其实移除的是上一块石头。但这样做代码容易绕晕。做法二更推荐单独处理。先把中间 N 块石头按贪心扫完之后检查L - last是否小于 mid。如果小于说明最后一段不满足此时应该把last这块石头移走cnt。为什么因为起点和终点不能动想让最后一段变长只能移掉“最后一个保留的石头”。这一步很多人漏写但漏写之后还能过不少数据属于“运气型 AC”一旦边界数据出现就翻车。还有一个细节m 可以为 0一块都不能移这时二分答案退化成求原序列的最小相邻距离check 函数依然能正确处理cnt 会是 0检查cnt 0成立。n 也可以为 0中间没有任何石头这时答案就是 L二分时左右端点分别是 0 和 Lcheck(mid) 的处理是“只看终点距离”照样能得出 L。3.4 完整实现我把代码写出来注意我采用了“终点单独检查”的做法并在注释里标明关键逻辑。#include bits/stdc.h using namespace std; long long L, n, m; long long d[50005]; bool check(long long mid) { int cnt 0; long long last 0; // 上一块保留石头的位置从起点开始 for (int i 1; i n; i) { if (d[i] - last mid) { cnt; // 距离太短移走当前石头 } else { last d[i]; // 保留当前石头 } } // 终点单独检查最后一段若不够长只能移走最后保留的石头 if (L - last mid) cnt; return cnt m; } int main() { cin L n m; for (int i 1; i n; i) cin d[i]; long long l 0, r L, ans 0; while (l r) { long long mid (l r) / 2; if (check(mid)) { ans mid; // 距离 mid 可行尝试更大 l mid 1; } else { r mid - 1; // 距离 mid 不可行降低要求 } } cout ans endl; return 0; }二分方向要反复确认mid 越大每一跳要求越高需要移走的石头越多可行性越弱。一旦 check(mid) 可行说明我们还能把要求提得更高所以答案在右侧也就是l mid 1。这和砍树题一致都是“最大化可行值”的方向。我第一遍写这题时二分判断写反了——check 成立时往左缩结果样例碰巧过大样例全错。后来想明白你认为是“能不能更大”还是“要不要更小”取决于单调性是递增还是递减。跳石头中“可不可行”随 mid 增大而递减从真变假所以 check 为真要往右找。希望你不要在这个地方浪费一整晚。4. 两题放一起看二分答案的识别套路、常见翻车点和进阶方向4.1 对比表格直接求 vs 验证、最大值 vs 最小值把砍树和跳石头放在一起对比二分答案的全貌就浮现出来了。两题表面上不同底子是完全一致的。对比维度砍树跳石头答案类型最大的可行锯片高度最大的最小跳跃距离直接求解难度难更难有点抽象check 的验证方式求和比较贪心模拟移石头check 时间复杂度O(N)O(N)单调性h 越大总木材量越小mid 越大越难满足check(mid) 成立时往右搜尝试更大 h往右搜尝试更大 mid经典隐蔽坑不开 long long 溢出终点最后一段未检查你会发现两个题的 check 成立时做的动作一模一样记录 ans然后尝试往更大的方向走。这是“最大化可行答案”这一类题的共同骨架。反过来如果是“最小化可行答案”比如求最小速度、最小成本check 成立时要往左搜。把方向问题整理清楚比多刷十道题都管用。4.2 识别套路看到最大化最小值/最小化最大值就想到二分答案什么样的问题可以套二分答案我在实战中总结了三个识别特征满足度越高越应该往这个方向想。特征一答案是一个连续区间的整数或实数。比如高度、距离、速度、时间、成本而不是一个复杂结构。特征二直接求最优解困难但验证一个给定的解是否可行很容易。这个要靠经验判断刷多了自然有感觉。特征三可行性关于答案具有单调性。最常见的就是“资源越多越容易满足”或“要求越高越难满足”。关键词口令“最大值最小”“最小值最大”“最小距离的最大值”“最大速度的最小值”。看到这些表述第一反应就应该是二分答案。比如经典的最长上升子序列的优化、月度开销的分组问题、电网负载均衡……本质都是这个套路。还有一个非常常见的搭配二分答案 贪心 check。跳石头就是典型二分负责在外层缩小答案范围贪心负责在内层快速验证。很多难题都是“二分答案 DP check”或者“二分答案 前缀和 check”但核心思想完全一致。所以把砍树和跳石头的 check 写法吃透等于给后续所有二分类题目打好了地基。4.3 实数二分的简单说明整数二分之外有些题目答案是实数比如求“最小速度”可以是 3.14。这种题二分框架不变只需要注意三点。确定精度 eps。通常题目要求保留 k 位小数就给 eps 1e-(k2)也就是比输出精度高两位以上。比如保留两位小数eps 用 1e-4 比较稳。循环条件用精度控制。写成while (r - l eps)而不能用l r——因为实数二分的 l、r 永远不可能精确相等。当心精度引起死循环。如果 eps 开得过小比如 1e-12有些大数据会陷入长循环甚至死循环。经验值是输出要求保留 k 位就设 1e-(k2)不要贪心。整数二分的“死循环”问题则完全不同通常出在边界条件上。如果你用l r而不是l r配合不同的 mid 取整方向有可能在区间收缩到相邻两个数时陷入死循环。我的习惯是尽量用l rans去记录逻辑统一省心。4.4 常见翻车点速查最后把我这些年见过的二分答案翻车点汇总成一个清单每条都是真实踩出来的经验不是书本上的教条。方向搞反check 成立时该往大走还是往小走取决于“可行性-答案”的单调方向不是记模板就能偷懒的推理一遍再写代码。没开 long longN、M、数组值、中间累加值都可能超过 int宁可全开 long long 也别省。ans 没有单独存漏了ans mid只用 l/r 作为最终答案边界数据下容易输出一个不可行值。check 里等号取错写成写成边界数据立刻挂。跳石头里距离正好等于 mid 时应该保留石头不能移这个等号就是生死线。跳石头终点漏检查最后一段距离不满足时没有处理小数据能过大数据随机挂。二分域没有包住正解砍树右端点是最高树跳石头右端点是河道总长 L。就算答案是边界值比如 m0 时跳石头答案就是原序列的最小间距也一定在 [0, L] 内也要保证区间充分覆盖。我自己刷二分答案题也有一个经验习惯每道题先写 check 函数再写二分主循环。因为 check 是题眼是承载单调性的地方主循环只是机械地利用单调性缩小区间。如果 check 写错了二分写得再漂亮也没有意义。反过来check 写对了即使二分模板不太熟也能靠推理补齐。另一个很实用的小技巧写完代码后用题目给的样例跑一遍然后手动把样例中可能触发边界的值打出来试试比如砍树时设定 M 等于 0 或等于砍完全部树的总量跳石头时设定 m 等于 0 或 n。这些零界点能快速暴露方向写反和等号写错的问题比看十遍代码都有效。这两道题刷透之后二分答案的骨架基本就立住了。之后遇到更复杂的二分题你真正要思考的只剩一件事check 函数用什么技术去写是贪心、DP、还是某种数据结构。至于二分的壳子它已经把答案的搜索空间压缩到了 log 级别剩下的全是验证的艺术。