二分答案从入门到实战：两道经典题彻底搞懂算法套路

做算法题这些年有个技术点让我印象特别深二分答案。第一次在题目上看到“二分答案”这个标签时我其实挺懵的——二分查找我熟有序数组里找值嘛但“二分答案”是什么答案还能二分后来在洛谷上把两道经典题亲手写明白才彻底搞懂这个套路。这篇文章就把我从理解到掌握的全过程记录下来适合刚学完二分查找、正准备进阶二分答案的读者也适合刷题时碰到“最大值最小”“最小值最大”这类描述就头皮发麻的同学。1. 先把“二分答案”是什么讲明白1.1 它和普通的二分查找差在哪普通二分查找针对的是数组。数组有序你拿着目标值每次通过比较中间元素来排除一半范围最后定位到元素下标。整个过程的核心是“在一个已知集合里找一个精确的值”。二分答案不太一样。它二分的不再是数组下标而是一个“答案区间”。这个区间往往是一个连续的整数范围比如“锯子的高度”“最短跳跃距离”“最大载重”你需要在这个区间里找到那个满足条件的“最优解”。这里的难点是最优解不能直接算出来只能靠“试”。怎么试给定一个候选答案x你写一个函数能快速判断它是否可行如果可行你再往大的试或者往小的试不可行就往反方向试。这个“试”的过程因为每次排除一半的区间所以效率很高。生活里有个很贴切的例子猜价格。主持人心里想一个数字让你猜你每猜一次他只告诉你“高了”还是“低了”。你肯定不会从1块开始一块一块往上加而是直接报500听完反馈后把范围砍半再报250或者750。二分答案干的就是这件事每个候选答案相当于你猜的一个价格“可行”还是“不可行”相当于主持人告诉你“低了”还是“高了”。只不过这个“主持人”是你自己写的一个check函数。1.2 单调性二分答案能成立的根基聊到这里你可能会问是不是随便猜个区间都能二分当然不是。二分的前提是“可行性必须随着答案单调变化”。用猜价格举例主持人心里想的那个数你往高了报他不说“高了”往低了报他也不说“低了”那这个游戏就没法玩。算法的道理一模一样。假设我们要找最大的可行答案x那么x小时时候可行x大的时候不可行中间一定有一个临界点。这个临界点就是最优解。反过来如果你要找的是最小的可行答案那x小的时候不可行x大的时候可行临界点同样是最优解。这就是二分答案的全部思想基础。后面两题的check函数本质都是在验证一件事给定这个候选值题目条件成不成立。而这个“成立”随候选值的单调变化就是我们敢用二分的底气。2. 第一题砍树一个模板吃透最基础用法2.1 题意拆解为什么答案是二分出来的砍树这道题非常经典它来自洛谷的P1873EKO题目大意是有n棵树每棵树有个高度。现在你要定一个锯子的高度H锯子会砍掉所有高于H的部分把这些砍下来的木材收集起来。你至少需要m米的木材问H最大能取多少。举个例子三棵树高度分别是5、10、15你定H10那么只有第三棵树会被砍掉5米总木材是5米。如果你定H5三棵树砍下来分别是0、5、10总共15米。但H太高的话可能一棵树都够不到木材直接是0。注意这里问的是“H最大能取多少”。H越大木材越少越难满足“至少m米”的需求H越小木材越多越容易满足。所以如果定义check(x)为“锯子高度为x时能不能砍到至少m米的木材”那么check(x)的结果是x小的时候成立x大的时候不成立。我们要找的就是那个“仍然成立的最大x”。为什么不直接算因为你没法通过公式一步求出H。虽然每棵树的贡献是max(0, h[i]-x)但你要反推x没有一个简单的求逆运算。而验证一个x是否可行只需要遍历一遍所有树O(n)搞定非常快。2.2 判定函数 check 这样写check函数的逻辑特别直白给定一个高度x把所有树高于x的部分加起来看看总木材是否大于等于m。bool check(long long x) { long long sum 0; for (int i 1; i n; i) { if (h[i] x) sum h[i] - x; if (sum m) return true; // 已经够了提前返回 } return sum m; }这里有一个细节很多人会忽略sum的类型必须用long long。假设有10万棵树每棵树高10亿H取0那sum理论上能到10的14次方int根本装不下。竞赛题里这个坑特别隐蔽样例能过一提交就WA答案错误十有八九就是类型爆了。第二个细节是提前返回。当sum累计到超过m可以直接return true没必要继续遍历。这个优化在大数据下能省不少时间尤其是当答案偏小木材很快就能凑够的时候。2.3 二分框架与完整代码二分答案的框架和二分查找长得像但有细微差别。强烈建议初学者用“ans记录法”也就是二分循环里只要check通过就把当前mid记录到ans里最后直接输出ans。为什么这么做因为当check(mid)成立时mid可能是答案也可能答案比mid更大反正mid是“目前已知的可行解里最好的”。你把它记下来万一下一次查找的mid不可行你还有上一次的可行解保底。这样比最后输出l还是r更不容易出错。砍树这题的l和r取值是l0表示锯子高度为0所有树全砍r最高那棵树的高度因为锯子高度只要超过最高树一棵树都砍不到木材必定为0显然不成立。答案一定在[0, maxH]这个区间里。#include bits/stdc.h using namespace std; typedef long long ll; const int N 1000010; int n; ll m, h[N]; bool check(ll x) { ll sum 0; for (int i 1; i n; i) { if (h[i] x) sum h[i] - x; if (sum m) return true; } return sum m; } int main() { scanf(%d%lld, n, m); ll maxH 0; for (int i 1; i n; i) { scanf(%lld, h[i]); maxH max(maxH, h[i]); } ll l 0, r maxH, ans 0; while (l r) { ll mid (l r) / 2; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%lld\n, ans); return 0; }这个模板的循环条件是l r每次l和r更新时都各自加1或减1所以不会出现死循环。又因为mid总是落在[l, r]区间内且每次check之后区间都会缩小所以循环必终止。2.4 这一题最容易犯的错我第一次写这道题的时候把l初始化成了1结果样例里有一组答案是0的情况直接输出错误。原因就是如果m特别大锯子高度必须低到0才能凑够木材那答案就是0。l从1开始mid取不到0自然错了。所以上下界一定要覆盖完整答案区间这是二分答案最容易翻车的地方。还有一个很多人问过的问题为什么答案范围不是从1到10^9枚举要用二分你可以算一下n10^5如果从maxH往下每减1就做一次check最坏要操作10^9次肯定超时而二分只做约log2(10^9)≈30次check每次O(n)总共300万次操作轻轻松松过。3. 第二题跳石头判断函数从“算”变成“模拟”3.1 题目转化最大最小距离怎么判搞定了砍树二分答案的框架算是入门了。但只做砍树还体会不到二分答案的精髓因为砍树的check函数就是一个简单的求和。第二题跳石头NOIP原题P2678才是真正考验思维的地方。题目大意从起点到终点有一条河起点位置是0终点位置是L中间有n块石头每块石头在距离起点d[i]的地方。现在你可以移走最多m块石头移完之后选手要从起点踩着石头跳到终点问你“移完之后任意相邻落脚点含起点终点之间的最小距离”最大能是多少。“最小距离最大”这种描述一出现基本就是二分答案的信号。原因是如果你把“最小距离”定成一个候选值x那么“能不能通过移走不超过m块石头让所有相邻石头间距都不小于x”这件事是一个非常好验证的判定问题。而且可行性随x单调变化x小当然容易满足x变大需要移走的石头越来越多一旦超过m就不可行。我们要找的就是临界点上那个最大的可行x。3.2 check 的贪心模拟过程这道题的check函数不再是求和而是用一个贪心的模拟过程。假设我们正在验证“最小距离至少为x”是否可行。核心思路是从左往右遍历每一块石头尽量保留离起点近的石头。我们从起点出发维护一个变量last表示“上一块被保留的石头的位置”。遍历每块石头如果当前石头和last的距离小于x说明这块石头和上一块保留石头的间距不够那当前这块石头必须被移走此时计数器cnt加1否则这块石头可以保留把last更新为当前石头的位置。为什么这个贪心是对的因为如果当前石头和上一块保留石头距离不够x那当前石头无论如何都不能保留——留着它只会徒增一个过近的相邻距离而且它不会帮助后面的石头更近所以移走它是最优决策。这里有个坑循环结束后还要检查终点到last的距离。因为终点是固定位置不能被移走如果终点和最后一块保留石头之间的距离小于x那这个x是不可行的。注意这个坑太经典了很多人循环里写得挺顺结果忘了终点直接白给。bool check(int x) { int cnt 0, last 0; for (int i 1; i n; i) { if (d[i] - last x) cnt; else last d[i]; } if (L - last x) return false; return cnt m; }注意这里的返回值。如果终点距离不够不管cnt是多少都直接return false因为终点没法移走。如果终点距离够再判断移走的石头数量cnt是否没超过m。两者都满足这个x才成立。3.3 完整代码和边界处理二分区间上l可以设为1因为最短距离至少是1都是整数点距离不会小于1r设为L因为最大最小距离不可能超过起点到终点的总长度。但如果你为了稳妥也可以把l设成0答案区间就变成了[0, L]。实测下来这两种都没问题但习惯上我把l设成1能少一次判断。#include bits/stdc.h using namespace std; const int N 50010; int L, n, m; int d[N]; bool check(int x) { int cnt 0, last 0; for (int i 1; i n; i) { if (d[i] - last x) cnt; else last d[i]; } if (L - last x) return false; return cnt m; } int main() { scanf(%d%d%d, L, n, m); for (int i 1; i n; i) scanf(%d, d[i]); int l 1, r L, ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%d\n, ans); return 0; }这道题有个地方比砍树更好玩check函数里的“移走”是虚拟的你并没有真正修改数组。每次二分出一个mid都重新从0开始模拟。因为二分的次数很少每次模拟O(n)整体效率非常高。这比你想一个真正的“移除方案”去求答案要容易太多。3.4 两道题放在一起看check 的两种形态把砍树和跳石头放在一起看你会发现二分答案的代码框架几乎一模一样变的只是check函数里的逻辑。砍树的check是“直接计算总量”跳石头的check是“贪心模拟过程”。这两种形态可以覆盖绝大多数二分答案题目计算型给你一个可行值x你直接算出某个总量或指标再和限定值比较。比如砍树、木材加工、月度开销这类。模拟型给你一个可行值x你按照某种贪心策略去装、去分、去跳看最终能不能满足约束。比如跳石头、进击的奶牛、数列分段。所以你看学二分答案本质上是在学两种东西一是学会判断能不能用二分二是学会针对题目设计check函数里那个“贪心/计算”逻辑。框架永远是那个框架。4. 提炼成通用套路从两题上升到模板4.1 什么时候能想到二分答案我见过不少同学看完题解觉得二分答案好简单可一到自己做题就想不到。其实二分答案的题目特征非常明显你可以在做题时用一个四步判断法第一步题目问的是最大值或最小值。尤其出现“最大值最小”“最小值最大”“某个值最大是多少”这类字眼。第二步答案落在某个连续的整数区间内而不是某个离散的集合里。第三步存在一个check函数能在多项式时间内验证一个候选答案是否可行。第四步check的结果随答案单调变化。单调递增或单调递减都行但必须单调。如果以上四条都满足那基本就能锁定二分答案。还有一些间接的信号比如题目数据范围特别大1e5以上而且你发现除了枚举答案外没有别的直观思路那也该往二分答案上想一想。4.2 一个通用模板和两个方向二分答案的代码模板我推荐下面这种“ans记录法”它是我实测踩过各种边界坑之后最稳的写法int l 0, r INF, ans 0; while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; l mid 1; // 往更大的答案方向试 } else { r mid - 1; // 答案太大了往小的方向试 } } printf(%d\n, ans);这套模板适用于“找最大的可行解”也就是check(mid)为true时我们要向右收缩。至于“找最小的可行解”只需要在check(mid)为true时把r mid - 1并记录ans即可while (l r) { int mid (l r) / 2; if (check(mid)) { ans mid; r mid - 1; // 往更小的答案方向试 } else { l mid 1; // 答案太小了往大的方向试 } }这两个方向只要想清楚你需要的是“更大”还是“更小”就不会写反。如果实在拿不准就在纸上画一条数轴标出可行域在哪一侧闭着眼都能写对。4.3 mid 的取整方向和死循环问题有些同学习惯用l r的写法也就是while (l r) { int mid (l r) 1; if (check(mid)) l mid; else r mid - 1; }这个写法有个著名的坑当check(mid)成立时你执行l mid但如果mid恰好等于l而l又小于r那l永远不变就死循环了。比如l3r4mid(34)/23check(3)成立l还是3区间永远不缩。解决方法是把mid改成(l r 1) 1向上取整。这也是为什么很多人说“整数二分要加1”。我个人的建议是新手期老老实实用l r加ans记录的写法它天然避开死循环问题少受罪。等你用熟了再回头尝试l r的写法也不迟。5. 实操避坑记录这些细节害我调了半天5.1 check 里提前返回的坑砍树的check里sum够了可以提前return true这个优化安全且高效。但并不是所有check都能这么干。跳石头这种需要完整模拟的题目如果你在遍历途中发现cnt已经超过m可以提前return false因为再往后遍历cnt只可能增加不可能减少。但是有一种情况千万别提前返回如果check函数后半部分还依赖前面累计的状态而你提前跳出了就会漏掉关键判断。比如跳石头你如果在循环里发现cnt超过m就提前返回false这没问题但你如果在终点距离还没判断时就提前return true那就大错特错了。我见过有人把砍树的提前返回习惯搬到跳石头里结果终点判断被跳过WA得莫名其妙。提前返回的原则是确认影响最终结论的信息已经全部处理完才可以提前跳。5.2 上下界设置不当直接错二分答案的上下界是另一个高频出错点。上界太大会导致多出无效二分但通常不会WA真正致命的是下界设置得太高导致正确答案被排除在区间之外。砍树那题如果你把l设成1而答案是0结果就会错。跳石头那题如果你把l设成1而实际答案可能是0所有石头都可以被移走但终点距离仍然存在仔细想想其实答案最小是1但如果你是移走所有中间石头后起点到终点距离L最短距离仍是L所以答案一定是正数。这种边界分析必须具体题目具体处理。我的习惯是先把答案可能的最小值写出来常常是0或1再把答案可能的最大值写出来常常是题目里的某个上限比如最高树高、总长度、最大载重然后把这两个值分别赋给l和r。宁可范围稍微大一点也不要漏掉正确答案。5.3 常见问题速查表最后整理一个自查清单每次写完二分答案可以对照检查一遍基本能解决九成的问题。问题现象排查方向答案少1或大1看l和r更新时是否该±1是否用了ans记录死循环检查是否为l r且mid下取整导致区间不缩大数据下WA检查sum、cnt等变量类型用long long边界答案出错检查l、r初始值是否覆盖了答案区间样例过但全错check里的比较方向写反比如写成超时check内部是否该提前返回二分次数是否过多还有一个调试小技巧当你怀疑是二分答案的问题时可以在二分循环里输出l、r、mid和check(mid)的结果手动跑一遍小数据看看区间收缩的方向是否正确。很多时候不是模板的问题而是check的方向写反了一输出立马就能看出来。我个人在两题刷完之后最大的体会是二分答案并不是什么高深技巧它只是把“求解”换成了“判定”再用单调性让判定的次数变成log级别。你真正要练的其实是两件事一是判断题目能不能二分答案二是为自己的题目写出那个正确的check函数。这两件事熟练了二分答案就是一个顺手就能用的套路后面的粉刷匠、数列分段、月度开销等题目也都是一路通吃。如果你正在学这个套路别急着背模板先打开编辑器把砍树和跳石头亲手敲一遍敲完你自然就懂我说的意思了。