去年带训练队的时候有个学弟拿着 POJ 3273 跑来找我问了一个让我印象很深的问题“学长我明白二分查找但为什么这道题也在二分它到底在二分什么”这个问题几乎是每个刚接触二分答案的人都会卡住的地方。你背过二分查找模板知道在有序数组里查一个数但二分答案里既没有有序数组也没有要查的目标值看起来完全不是一回事。更让人头疼的是同样是二分有的题要求“最大值最小”有的题要求“最小值最大”光是把这两个方向搞清楚就能劝退一大半新手。这篇文章我想把二分答案这件事彻底拆开讲清楚重点就是“最大”和“最小”这两类模型到底有什么区别、check 函数应该怎么写、二分边界应该怎么收缩以及我在实际刷题和带训练过程中踩过的坑。不管你是准备 CSP/NOIP 的竞赛生、要应付机试的考研党还是刷 LeetCode 面试题的选手这套东西都值得花一下午彻底吃透。1. 二分答案到底在“二分”什么1.1 二分查找与二分答案一字之差对象完全不同先说结论二分查找的对象是数组下标二分答案的对象是答案的取值范围。二分查找的场景很固定一个有序数组你要找某个 target 的下标。每次取中间位置比较大小然后向左或向右收缩。它利用的是数组元素的“有序性”。二分答案则完全不一样。它面对的问题往往没有一个现成的有序数组只有一个让你摸不着头脑的问题比如“把数组分成若干段让最大值最小”。这时候你不需要直接去构造最优方案而是去“猜答案”再写一个函数来验证这个答案行不行。我常用一个生活类比解释你去批发市场买一批零件卖家说单个成本在 100 到 200 块之间你想知道最低谈到多少钱能保证质量合格。你不会让卖家把每个价格都试一遍而是先报一个价比如 150问这个价能供货吗。能就往下压不能就往上加。每报一次价就是一个 check 过程。二分答案做的就是这个事。所以二分答案的核心思想可以提炼成一句话把“求最优解”转化成“判定一个值是否可行”。这也是它和普通二分查找最大的区别——前者在“猜答案”后者在“找目标”。1.2 把“求最值”翻译成“判可行性”很多同学第一次接触二分答案时最大的障碍是思维惯性。看到一个求最值的题第一反应是先想怎么构造最优方案。但二分答案直接反过来了我根本不需要知道最优方案长什么样只需要能判断某个答案可不可行。举一个最经典的例子。给你一个长度为 n 的数组要求按顺序分成不超过 m 段希望所有段的和的最大值尽量小。如果直接构造方案你得考虑每一段从哪里断开这本质上是个枚举切割点的组合问题复杂度非常高。但如果你换一种问法给定一个数 x我能不能用不超过 m 段让每一段的和都不超过 x这个问题就好答多了。我从左到右扫一遍数组能塞进当前段就塞塞不下就新开一段最后数一数用了多少段。只要段数不超过 m就说明 x 是可行的。看到没有整个思路的关键变化就在这里从“构造最优解”变成了“验证某个解是否成立”。而验证往往比构造简单得多因为它只关心“能不能做到”不关心“具体怎么做到最好”。二分答案就是把这种“验证能力”利用到了极致——既然验证一个答案很容易那我就在答案的范围里二分搜索每次验证一下最终逼近最优解。2. 二分的前提单调性决定一切2.1 可行性随答案变化必须单调不是所有求最值的题都能用二分答案能用它有一个大前提答案的可行性必须是单调的。什么叫单调我们拿两类典型问题来看。第一类是“最大值最小化”。设答案为 xx 越小代表要求越严格。x 很小的时候方案几乎没法满足check 返回 falsex 慢慢变大约束变松某一天开始 check 变成 true之后一直保持 true。整个序列是 false、false、true、true、true……这种形态就是单调的。第二类是“最小值最大化”。x 很小时条件非常宽松随便放都能满足check 返回 truex 越来越大要求越来越苛刻某一天开始 check 变成 false之后一直 false。序列是 true、true、false、false……同样是单调的。这个单调性决定了二分的可行性你拿到一个 mid如果它可行你就可以判断最优解在 mid 的哪一侧如果它不可行又可以判断在另一侧。只要能这样不断缩小范围最终就能锁定答案。2.2 不单调会出现什么问题有些同学可能会想如果 check 函数本身写得不对或者题目本身不具备单调性二分还会生效吗答案是不仅不生效还会给出完全错误的答案。假设一个题目的可行性序列是 true、false、true你二分到中间那个 false 时会以为答案在右侧但实际上左侧也有可行值于是正确答案就被错过了。这就是为什么写二分答案之前一定要先在草稿纸上画一下x 特别小的时候 check 是什么x 特别大的时候 check 是什么中间是不是连续过渡的。我自己的习惯是拿到题先手算三个值一个特别小的 x、一个特别大的 x、一个中间值。把这三个值的 check 结果写出来如果发现它是 0/0/1 或者 1/0/0 这种非单调的情况就说明这题不适合二分答案得换思路。还有一个容易踩的坑有的同学以为二分答案要求“原数组有序”这是错的。二分答案本身不依赖原数组顺序但 check 里的贪心逻辑往往要求你先把数据处理成有序的比如二分最大间距前要先给坐标排序。后面 POJ 2456 的例子里我会专门再强调这一点。3. 最大与最小核心模板与原理3.1 最大值最小化让“最重的那段”尽量轻最大值最小化这类问题的典型问法是“最大值最小”“最重的尽量轻”“最长的一段尽量短”“让最大的开销不超过多少”。碰到这种表述你要马上反应过来这是在二分“最大值”本身。以 POJ 3273 Monthly Expense 为例。题目给了 n 天的每天开销要求把这 n 天按顺序分成恰好 m 个月希望“月开销最大值”最小输出这个最小值。首先确定二分对象我们要猜的数就是一个“月开销上限 x”。然后用 check(x) 判断在每个月开销不超过 x 的前提下最少能分成多少段。check 的写法很经典bool check(int x) { int cnt 1; // 至少有一段 int cur 0; // 当前段累计开销 for (int i 1; i n; i) { if (a[i] x) return false; // 单日开销已经超过上限直接不可行 if (cur a[i] x) { // 当前段放不下开新段 cnt; cur a[i]; } else { cur a[i]; } } return cnt m; // 关键最少段数不超过 m 就算可行 }这里有一个让很多人困惑的点题目要求“恰好分成 m 段”为什么 check 里判断的是cnt m而不是cnt m原因很简单如果最少只需要 cnt 段就能满足“每段和不超过 x”那你完全可以把其中某些段再拆开段数变多但每段和依然不会超过 x。也就是说只要最少段数不超过 m就一定能通过拆分凑出恰好 m 段。反过来如果最少段数都超过 m 了那任何合法的 m 段划分都不存在。完整的主函数二分部分int l 0, r 0; for (int i 1; i n; i) { l max(l, a[i]); // 下界单日最大开销 r a[i]; // 上界所有开销之和 } while (l r) { int mid (l r) 1; if (check(mid)) { r mid; // x 可行试试更小的 } else { l mid 1; // x 不可行必须放大 } } printf(%d\n, l);注意初始下界为什么是数组最大值而不是 0。如果下界小于单个元素的最大值check 里会直接因为a[i] x返回 false虽然二分也能一步步往上逼近但会多跑很多无效迭代。直接从单日最大开销开始能省掉一截搜索空间。3.2 最小值最大化让“最近的那对”尽量远另一类是“最小值最大化”典型问法是“最小值最大”“最近的距离尽量远”“让最小的间隔越大越好”。POJ 2456 Aggressive Cows 就是这类题的代表。题目说有 n 个隔间坐标给定要把 c 头牛放进这些隔间希望任意两头牛之间的最小距离尽可能大输出这个最大化的最小距离。同样先确定二分对象我们要猜的数是“允许的最小间隔 d”。然后 check(d) 判断在任意两头牛距离至少为 d 的前提下最多能放几头牛。check 的写法用贪心bool check(long long d) { int cnt 1; // 第一头牛放最左边的隔间 long long last x[1]; // 上一头牛的位置 for (int i 2; i n; i) { if (x[i] - last d) { cnt; last x[i]; } } return cnt c; // 关键最多能放的牛数 c 就算可行 }这里又有一个“为什么不是等于”的问题。题目要求放恰好 c 头牛但 check 里判断的是cnt c。理由和上一题类似如果间距 d 下能放下超过 c 头牛那你随便挑其中 c 头放最小距离仍然不小于 d所以条件成立。反之如果最多都放不满 c 头牛那任何方案都无法满足。另外注意第一头牛一定要放在最左边的隔间。这是因为放得越靠左后续牛的选择空间就越大不会损失可放数量。这是贪心成立的关键局部最优选择能带来全局最优数量。主函数二分部分sort(x 1, x n 1); // 坐标输入顺序不定必须先排序 long long l 0; long long r x[n] - x[1]; // 最大可能距离 while (l r) { long long mid (l r) 1; if (check(mid)) { l mid 1; // d 可行试试更大的 } else { r mid - 1; // d 太大缩小 } } printf(%lld\n, r);注意这题我用了while (l r)和上一题的while (l r)不一样。原因在于两类问题的答案存储位置不同最大值最小化当 mid 可行时正确答案可能更小所以我们收缩右边界 r mid最后 l 就是答案。最小值最大化当 mid 可行时正确答案可能更大所以我们扩大左边界 l mid 1但最后一次可行的 mid 会被保存在 r 中所以循环结束后输出 r。如果你觉得每次都要想“输出 l 还是 r”很晕有一个更通用的写法用一个 ans 变量记录最后一次成功的位置。long long ans 0; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; // 这个答案可行先记下来 l mid 1; // 继续找更大的 } else { r mid - 1; } } printf(%lld\n, ans);这种写法虽然多一个变量但逻辑非常清晰每次 check 成功就更新 ans循环结束后 ans 一定是最优解。我在实际做题时更推荐这个写法可以少想很多边界问题。3.3 一张表对比两种套路为了让你一眼分清两类问题的差异我把核心区别整理成一张表对比项最大值最小化最小值最大化题干关键词“最大值尽量小”“最重的尽量轻”“最小值尽量大”“最近的尽量远”二分对象被最小化的那个“最大值”被最大化的那个“最小值”check(x) 为 true 的含义x 这个上限可行x 这个下限可行可行时收缩方向尝试更小的 xr mid - 1尝试更大的 xl mid 1不可行时收缩方向l mid 1r mid - 1典型输出l 或记录最后一次 true 的位置r 或记录最后一次 true 的位置做题时先看题目问你的是“最小化什么”还是“最大化什么”再去确定二分方向和 check 逻辑。这个判断比背模板重要得多。4. 实战拿到题目怎么快速套模板4.1 五步拆题法很多同学背了一堆模板一到新题还是不会用。我总结了一个五步流程每次拿到题都按这个顺序走读题确定目标把题目要求翻译成“我要最大化什么”或“我要最小化什么”。圈出题干里的“最大/最小”关键词。确定二分对象找到那个被优化的参数。它通常就是你最后要输出的那个值。设计 check 函数问自己一个问题——“如果我知道了答案 x能不能在 O(n) 或 O(n log n) 时间内判断 x 是否可行”这个问题的答案决定了二分答案能不能用。确定上下界下界往小想上界往大想但可以结合题目数据缩小范围。比如数组最大值、坐标最大差值、所有元素之和等。写二分循环根据“可行时往哪边收缩”确定模板方向建议用 ans 变量记录中间成功结果避免 l/r 输出混乱。这五步里最容易出错的是第三步。很多人纠结模板细节却忽略了 check 本身才是二分答案的灵魂——模板只是骨架check 是大脑。4.2 完整过一遍 POJ 2456拿上面说的五步法我们完整走一遍 POJ 2456。第一步读题。“最小距离尽可能大”这是经典的最小值最大化。第二步二分对象是“允许的最小间隔 d”。第三步check 函数就是上面的贪心模拟给定 d最多能放多少头牛。第四步上下界下界取 0因为距离至少为 0上界取排序后最大坐标减最小坐标因为不可能有更大的间隔了。第五步可行时向右找更大值用 ans 记录。完整可提交的代码#include bits/stdc.h using namespace std; const int N 100010; int n, c; long long x[N]; bool check(long long d) { int cnt 1; long long last x[1]; for (int i 2; i n; i) { if (x[i] - last d) { cnt; last x[i]; } } return cnt c; } int main() { scanf(%d%d, n, c); for (int i 1; i n; i) scanf(%lld, x[i]); sort(x 1, x n 1); long long l 0, r x[n] - x[1], ans 0; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%lld\n, ans); return 0; }几个容易错的地方我再强调一下坐标输入未必有序check 里的贪心必须按坐标从左到右扫描所以进入二分前一定要sort。第一头牛固定放最左隔间cnt初始从 1 开始不是 0。如果你从 0 开始会少算一头牛答案就会偏大。数据范围允许的情况下坐标用long long避免l r溢出。mid (l r) 1在极限数据下可能超出 int 范围这是竞赛里很常见的隐性 bug。4.3 完整过一遍 POJ 3273再用同样的流程看 POJ 3273。第一步读题。“月开销最大值最小”最大值最小化。第二步二分对象是“每个月开销的上限 x”。第三步check 函数给定 x按顺序贪心分段最少能分成几段判断是否不超过 m。第四步上下界下界取单日最大开销上界取所有天开销之和。第五步可行时向左找更小的 x用 ans 记录。完整代码#include bits/stdc.h using namespace std; const int N 100010; int n, m; int a[N]; bool check(int x) { int cnt 1, cur 0; for (int i 1; i n; i) { if (a[i] x) return false; if (cur a[i] x) { cnt; cur a[i]; } else { cur a[i]; } } return cnt m; } int main() { scanf(%d%d, n, m); int l 0, r 0; for (int i 1; i n; i) { scanf(%d, a[i]); l max(l, a[i]); r a[i]; } int ans 0; while (l r) { int mid (l r) 1; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } printf(%d\n, ans); return 0; }这里最值得记住的还是“最少段数不超过 m 就算可行”这个转化。很多人想不通为什么不是恰好等于 m其实你把“拆段”这个操作想清楚就明白了一组可以拆成两组不影响每段和的上限所以组数多一点也不怕只要最少组数能压到 m 以内后面随便拆都能凑出正好 m 段。5. 竞赛与面试中的坑我踩过的那些雷5.1 方向判断错误最大的坑最常见的 WA 原因是方向反了。最大值最小化的题用了“可行就往右找”最小值最大化的题用了“可行就往左找”本来该输出 l 的地方输出了 r。症状就是样例能过一提交就错。我自己的排查方法很笨但有效找一个很大的 x 和一个很小的 x分别手算 check 结果。如果 x 很小时 check 返回 false、x 很大时返回 true那题目方向就是“往左找最小可行值”如果反过来就是“往右找最大可行值”。只要这个方向判断对了二分模板基本不会错。5.2 二分死循环模板写法不匹配while (l r)配l mid或者r mid时如果 mid 的取整方向没配好很容易死循环。比如区间收缩到 l 2、r 3 时mid 2如果 check(2) 为 true 且你写了l mid那么 l 永远停在 2循环就出不来了。我推荐一个绝对稳妥的写法不管哪类问题都用while (l r)并且每一步都执行l mid 1或r mid - 1。因为 mid 每次都被排除出区间区间长度严格递减绝不可能死循环。再配合 ans 记录答案基本万无一失。5.3 溢出与数据范围二分答案经常涉及数组总和、坐标差、最大距离这类数值很容易逼近 int 上界。比如数组 n 1e5每个数 1e9总和就是 1e14int 早就爆了。我早期写 POJ 3273 时就用 int 存总和结果 WA 了一晚上换成 long long 马上过了。另一个细节是mid (l r) / 2时l r 可能溢出。虽然很多题数据没那么极限但保险起见推荐写成mid l (r - l) / 2或者直接用long long。5.4 check 内部细节贪心写错check 的问题往往藏在细节里。POJ 3273 的 check 里cnt初始为 1因为无论如何至少有一组。如果你写成 0最后判断cnt m时会多算一组导致结果偏小。POJ 2456 的 check 里第一头牛固定放最左端cnt初始为 1。如果你漏掉第一头牛从 0 开始数那结果会偏大。还有一点check 里要处理单点超过上限的情况。比如 POJ 3273 里如果某一天的开销本身大于 x那这个 x 无论如何不可行直接返回 false。这个判断漏掉的话贪心会把这一天单独成段仍然可能得到 cnt m 的错误判断。5.5 实数二分的精度控制有些二分答案题要求输出浮点数比如“最小半径”“最短时间”的浮点版本。这时候用 while (r - l eps) 很容易踩精度坑eps 设大了答案不够精确设小了循环跑不停。更稳的做法是固定迭代次数比如跑 100 次double l 0, r 1e9; for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) r mid; else l mid; } printf(%.10f\n, l);100 次迭代的精度远远超过 double 能表达的范围而且绝对不会死循环是竞赛里最省心的写法。5.6 问题速查表症状可能原因解决方法样例过了但 WA二分方向反了手算大 x 和小 x 的 check 结果程序卡死二分更新写错导致死循环改用 while (l r) 且每次排除 mid结果偏大check 里漏算第一项/第一头牛检查 cnt 初始值结果偏小判断条件用了 而不是 / 回到题目想清楚“恰好”怎么转化溢出用 int 存了总和或大距离改用 long long实数二分精度不对eps 设置不当用固定 100 次迭代6. 进阶二分答案的玩法不止两种6.1 二分答案 贪心 / DP / 差分二分答案最常见的是搭配贪心前面两道题都是这种组合。但 check 内部不一定是贪心也可以配合其他算法。当贪心不成立时可以在 check 里用动态规划。比如某些划分问题状态转移里需要判断段和是否满足当前二分的上限用一维 DP 就能完成验证。虽然复杂度比纯贪心高但二分的 O(log W) 因子通常可以接受。还有一种高频组合是二分答案 差分数组。典型场景是给定若干区间操作问你最少操作多少次能让某个最值达标。你把“操作次数”二分掉然后在 check 里用差分数组模拟全部操作O(n) 内判断是否可行。这类题在思维题和模拟题里出现频率很高。6.2 二分答案 数据结构如果 check 里需要动态维护一些信息比如区间最值、出现次数、前缀和等可以配合线段树、树状数组或平衡树来写。整体复杂度会变成 O(n log n log W)在 n 比较小的时候依然可跑面试题里偶尔会出现这种组合。我处理这类题的经验是先把 check 的朴素写法想清楚再考虑用数据结构优化。很多人一上来就套线段树结果 check 逻辑本身都是错的后面全是白搭。6.3 实数域二分与三分实数域二分的写法上面已经给过固定 100 次迭代是无脑选。三分法则用于单峰函数求极值和二分答案的“单调边界”是两种不同思路。前者找峰值后者找 0/1 边界。这个区别想清楚就不会把三分的题硬套二分答案。我自己带训练这几年见过太多同学把模板背得滚瓜烂熟一到新题就分不清往左还是往右。后来我教他们一个笨但有效的自检方法先别写代码找三个 x——一个特别小、一个特别大、一个中间值——手算 check 结果把 true 和 false 串起来。如果你能写出一个像 0/0/1/1 或 1/1/0/0 这样单调的序列这题就稳了如果写出来是 1/0/1 这种形状那赶紧换思路。二分答案表面上考的是二分实际上考的是你会不会写 check以及你敢不敢把“求最优”换成“猜答案”。这个思维一旦转过弯后面看很多题都会通透不少。我到现在写新题时还会下意识问自己一句如果我知道答案能在 O(n) 内验证吗能就值得往二分答案上想。