我在题库里刷题的时候遇到过这么一道题号P8088题目叫『JROI-5』Autumn难度标的是普及算法标签就四个字二分查找。当时第一反应是二分查找嘛代码二三十行的东西无非是while套mid几分钟就能AC。结果真正上手之后才发现问题根本不在二分本身而在于你能不能把一个看似复杂的判定问题压缩成一个单调的check函数。这些年我有个越来越强烈的感受普及这个难度段二分题是最容易拉开差距的。模板谁都会背但题目一变很多人就认不出这是二分了。今天借着P8088这道题我不打算复述原题面——网上搜一下就能看到——而是想把这套我从大量二分题里提炼出来的完整解题框架讲透。从二分的三种出题模型到边界处理的死循环问题再到check函数怎么写、复杂度怎么预算、对拍怎么调一次性讲清楚。这篇内容不挑具体语言示例代码我用C写但思路换到Python、Java一样通用。如果你正在备赛或者刚刷完一批二分模板题但碰到新题还是发懵这篇文章应该能帮你把背模板升级成建模型。1. 从P8088说起一道普及二分题暴露出的算法盲区先聊聊我为什么对这道题印象这么深。我当时是在一次集中的二分专题训练里遇到它的那次训练一共十道题从红题一路刷到提高P8088正好卡在中间偏前的位置。按我最初的想法这种题五分钟内应该能拿下结果我在边界和check的设计上反复折腾了一个多小时最后不得不打开题解才确认了自己的方向没问题只是实现细节抠得太粗糙。这种体验我相信很多人都有过。你问一个学过算法的人会不会二分查找他多半会说会但你要是给他一道没有明确有序数组字样的题让他自己发现该用二分他就卡住了。这说明什么说明大家背的是模板缺的是模型。1.1 为什么这道题会成为分水岭普及题目的典型特点是算法标签很直白但题面会给你绕弯子。P8088的标签写着二分查找可它真正想考察的不是在数组里找个数这种基础操作而是你能不能看出来答案可以二分。这里有个很现实的差距基础扎实的人看到题先想答案的值域再想check函数好不好写最后才决定要不要用二分只会背模板的人看到题满脑子都是mid (l r) / 2while(l r)一旦题目没有现成的有序序列模板就直接失效。我后来带过几个学弟学妹发现他们有一个共同的误区太把二分当成一种数据结构或者API而没把它当成一种解决问题的思路。实际上二分最强大的地方不在于查找而在于它能把一个求最优解的难题转化成一个判断某个值是否可行的简单问题。P8088这类题考的就是这种转化能力。1.2 很多人没分清二分查找并不等于二分答案这是我认为最值得先掰扯清楚的一点。二分查找Binary Search和二分答案Binary Search on Answer是两回事虽然代码长得几乎一模一样但思维模型完全不同。二分查找解决的是已知有序找位置数组已经有序你要找第一个等于/大于/大于等于目标值的位置。它的前提是序列单调比较的是元素本身。二分答案解决的是未知最值猜答案题目要求某种最大值或最小值你直接求很难但如果你猜一个答案x再去检查这个x是否可行检查的难度反而很低。于是你在答案值域里二分不断缩小范围最后逼近那个真正的最优解。拿P8088的标签来说它写的是二分查找但实战中这种普及题九成以上属于二分答案。如果只按查找来理解你根本无从下手按二分答案来理解思路一下子就顺了。这篇文章后面讲的所有内容也几乎都是围绕二分答案展开的。顺便提一嘴怎么快速判断一道题适不适合二分答案我有个经验法则题目里出现最大值最小最小值最大不超过某个数的最大值至少需要多少最远/最近/最快/最慢这类措辞并且直接贪心或枚举会超时那八九不离十是二分答案。不是所有极值题都能二分但有一大批都能。2. 读懂Autumn背后的二分模型三类常见出题套路P8088的题名是Autumn秋天的意思。说实话光看名字完全猜不到题面但竞赛题里这种文艺名字十有八九内部藏着一个分配、划分、分组型的问题——因为秋天总让人联想到收获、分割、打包这类意象。当然这是我的经验猜测真正解题时不能靠猜得靠模型。我把二分查找/二分答案的题目归成三大类基本覆盖了普及到提高组的所有考法。2.1 第一类有序序列上的直接二分这是最基础的玩法。数组已经有序或者题目允许你先排序再查询然后让你找某个边界位置。这种题属于送分题但手写实现时容易在边界上翻车。比如要在一个升序数组里找第一个大于等于x的位置标准写法是左闭右开区间int lower_bound_custom(int a[], int n, int x) { int l 0, r n; // 区间 [l, r) while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid; else l mid 1; } return l; // 第一个 x 的下标 }注意这里的mid我写的是l (r - l) / 2而不是(l r) / 2。两个数学上等价但前者能避免l r溢出。很多老手写模板时已经习惯性地这么写了新手容易忽略。这个习惯在答案值域很大的二分答案题里尤其重要后面第3节还会专门讲。如果题目允许用标准库lower_bound和upper_bound直接就能搞定。但竞赛里我始终建议能手写就手写因为二分答案的check函数里往往需要对多个不同值反复做边界查找手写不仅更灵活还能加深理解。2.2 第二类二分答案 可行性判定真正的重头戏这是普及二分题的主流模型也是P8088最可能采用的套路。它的结构用一个最经典的例子就能说明白把n个物品分成不超过m组问每组总和的最大值最小是多少。直接求最大值最小很难下手但如果你猜一个数x问每组总和都不超过x能不能分成不超过m组这就好办了——用贪心从左往右扫当前组放不下就新开一组看最后开了几组不超过m就说明x可行。这个检查函数就是我们要写的checkbool check(ll x) { int cnt 1; // 当前已经开了多少组 ll cur 0; // 当前这一组已经装了多少 for (int i 1; i n; i) { if (cur a[i] x) cur a[i]; else { cnt; cur a[i]; if (cnt m) return false; } } return true; }check(x)写完之后你会发现它是一个关于x的单调函数x越大每组容量越大越容易分完组所以check(x)从false变true的那个临界点就是我们要的最小可行值。而找最小可行值恰好就是二分最擅长的事情。这就是二分答案的完整流程确定值域范围写check二分逼近临界点。P8088如果真是这种模型那么你只需要做三件事第一步读题之后把答案值域定下来第二步把给定x判断可行性的check写出来第三步套二分模板。难点全在第二步而第二步考的是贪心、模拟、计数这些基础功。2.3 第三类二分套贪心、二分套DP普及的题目基本不会在这里出太难但你得有个意识check函数不一定只是简单模拟它内部可能是贪心、DP、最短路、网络流之类的高阶算法。二分只是外层枚举答案的手段真正的复杂度杀手是check内部的实现。打个比方二分是外挂的望远镜check是手里那把尺子。望远镜负责把答案区间快速缩小尺子负责精确测量每个候选值行不行。如果尺子本身是坏的望远镜再高级也没用。在复杂度上这两者是相乘关系。外层二分的次数一般只有30左右因为答案值域常见是1e9级别log2差不多30真正决定超不超时的是check的复杂度。比如check是O(n^2)那总复杂度就是30n^2n到1e5直接起飞check是O(n log n)那总复杂度30n log nn在1e5量级还能稳过。关于这个我后面专门用一个小节算给你看。3. 二分不死的关键区间写法、上下取整与终止条件二分题的代码总共就那么几行但新手最喜欢在这几行里翻车。死循环、答案错一位、边界越界、甚至样例都没过一半以上是区间写法没统一导致的。我在这节把三套主流写法都列出来并且明确告诉你每套的适用场景和容易踩的坑。3.1 三套区间模板选一套锁死第一套是左闭右开[l, r)适合查找型二分while (l r) { int mid l (r - l) / 2; if (条件满足) r mid; else l mid 1; }这套写法的好处是终止条件好判断l r就是答案。但它的更新方式比较受限一般只适合寻找第一个满足条件的值。第二套是闭区间 ans变量适合答案型二分ll l L, r R, ans -1; while (l r) { ll mid l (r - l) / 2; if (check(mid)) { ans mid; // mid可行先记下来 r mid - 1; // 继续往左找更小的可行值 } else { l mid 1; // mid不可行只能往右 } } cout ans \n;这套是我最推荐的也是我自己锁死的一套。它最大的优点是不管mid的取整方向是上取整还是下取整都不会死循环。因为每次更新都是l mid 1或r mid - 1区间长度必定严格减小。而且ans变量记录了最后一次可行的mid哪怕最后l和r交错答案也不会丢。第三套是闭区间[l, r]且不加ans的写法while (l r) { ll mid (l r 1) / 2; // 注意这个 1 if (check(mid)) l mid; else r mid - 1; }这套写法在找最大可行值时很常用但必须配合上取整否则死循环。缺点是不太好解释给新手稍不注意把mid写成(l r) / 2就卡住了。我不建议新手优先用它。三套模板各有各的适用场景但我的建议很明确平时只锁死一套做题时不要再临时切换。上考场时人的脑子是紧张的切换模板的思考成本往往就是WA的根源。3.2 mid取整方向与死循环的根源为什么上一节我说第二套最安全因为死循环的根源本质上就是mid取整方向和区间更新方式不匹配。举个例子你就明白了。假设你用的是第三套写法l 3, r 4区间里有两个值。如果mid按(l r) / 2下取整得到mid 3。假设check(3)为true执行l mid也就是l 3。这时候l还是3r还是4下一轮还是mid 3还是l 3无限循环。解决方法就是让mid上取整(l r 1) / 2这样mid 4执行l 4循环终止。反过来如果更新方式是r mid那mid下取整是安全的上取整反而可能死循环。简单记法l mid时必须上取整r mid时必须下取整。用第二套while (l r) ans就完全不用操心这个事因为l和r的更新全都跳过了mid本身。这也是为什么我一直强调初学阶段无脑锁死第二套就好。这里补充一个小细节上取整的写法(l r 1) / 2也有溢出风险稳妥写法是l (r - l 1) / 2。同理下取整写l (r - l) / 2。养成这个习惯后面处理1e18的答案区间你会感谢自己。3.3 溢出、负数区间与long long隐患二分答案题的值域经常是1e9甚至1e18级别int根本装不下。最直接的教训二分答案题不要声明int l、int r、int mid直接用long long所有check里涉及累加的变量也一起long long省得后面爆了再回头找。溢出场景不止是l r这一处。check函数里经常有当前段总和当前累计步数这类累加变量它们在判断x很大时也可能超过int。比如x接近1e18累加两次就爆了。统一long long是最省心的做法。还有一类题比较阴答案区间左端点不是0而是某个负值或者是一个由题目约束推出的下界。比如有的题答案范围是[-1e9, 1e9]你用mid (l r) / 2时l r恰好在int范围内倒是没事但用l (r - l) / 2才是绝对安全的写法。至于负数下取整C的整数除法向零取整这和数学上的向下取整不一致所以(l r) / 2在负区间上可能得到偏大的mid虽然配合ans模板不影响最终正确性但容易让人混乱。遇到负数区间我建议直接平移把所有值加一个偏移量变成非负再做或者老老实实用l (r - l) / 2并测试几个边界值。4. 判定函数check的设计与复杂度预算二分模板只是骨架真正决定这道题能不能做出来的是check函数。这节聊三个核心问题单调性怎么保证、check复杂度怎么算、以及怎么写一个不容易漏判的check。4.1 单调性是二分的命根子二分之所以能每次排除一半的区间依赖的是判定函数具有单调性。所谓单调性就是如果某个答案x可行那么比x更大或更小的答案也可行。拿前面分组例子来说如果每组上限x可行那么x 1一定也可行因为放宽上限只会让分组更容易。反过来如果x不可行x - 1通常也不可行。这种答案越大越可行的性质让我们可以放心地排除左半区间或右半区间。但并不是所有判定函数都单调。一个典型的反例是题目要求恰好分成m组那么一个过大的x可能导致分组数太少反而不可行一个过小的x会导致分组数太多也不可行。check(x)变成先可行后不可行再可行的波浪形二分就不灵了。怎么避免我有个习惯写check之前先在草稿纸上列三个x值——一个极小、一个中等、一个极大——手算check结果确认单调方向。这个习惯看起来蠢但对拍时能省下大量时间。很多WA题其实不是模板写错而是check函数的单调性从一开始就不成立。4.2 O(n)和O(n log n)的check分别能撑多大范围每次二分会调用check整个程序的运行时间就是二分次数 × check复杂度。二分次数好估算整数答案值域为C时约log2(C)次值域1e9就约30次值域1e18约60次。实数二分看精度一般固定100次循环。剩下的就是把check复杂度和数据范围匹配起来。下面这张表是我做题时心里默算的参考check复杂度外层二分30次后的总规模n的合适范围场景O(n)30nn ≤ 1e6 很稳贪心扫描、简单计数O(n log n)30 n log nn ≤ 1e5 很稳check内需要排序/堆O(n^2)30 n^2n ≤ 1e4 都悬只适合极小的nO(2^n)—n ≤ 25 还可能过状态压缩场景所以你看到一道n 1e5的普及题如果check只能写成O(n^2)那基本等于告诉你要么这道题不是二分答案要么你的check该换思路了比如用前缀和把内层循环优化掉。这个预算能力相当重要因为很多新手超时以后第一反应是二分次数太多了实则不是。二分次数30次几乎是零头真正的锅在check内部的多次排序或者多层循环嵌套。4.3 简化check的常见招数既然check要快那就有一些通用优化技巧。第一招是提前退出在check中一旦已经判定不可行或已满足立刻return不必把数组全扫完。比如分组时cnt一旦超过m就可以直接return false很多情况下能省下大半次扫描。第二招是把重复计算移到二分外面。比如check内部需要排序那这个排序一定不能在check里做要在外面先排好。check里做排序意味着每个mid都要排一次复杂度直接多乘30神仙都救不了。正确的做法是预处理阶段按某种规则排好序、算好前缀和check里只用下标访问复杂度降为O(n)甚至O(1)。第三招是用计数代替模拟。比如判断能否凑出x对满足条件的组合与其真的逐对枚举不如统计每个数值的出现次数再用组合公式快速判断。这类计数优化往往能把O(n^2)的check直接降到O(n)。5. 从通读到ACP8088的实战复盘与完整代码骨架理论讲完进入实际操作。这里我给出一份我能稳定AC的二分答案代码骨架附带对拍脚本和超时排查思路。你可以把这份骨架当成自己写题的底稿遇到具体题目只需要替换check函数和答案区间。5.1 一个稳过普及的二分答案模板先给一个可以直接抄的模板。以最经典的分组问题为例题目大概是把n个数分成不超过m段使每段和的最大值最小。#include bits/stdc.h using namespace std; using ll long long; const int MAXN 100005; ll a[MAXN]; int n, m; bool check(ll x) { ll cur 0; int cnt 1; for (int i 1; i n; i) { if (a[i] x) return false; // 单个元素就超上限直接不可行 if (cur a[i] x) { cur a[i]; } else { cnt; cur a[i]; if (cnt m) return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; ll sum 0, maxv 0; for (int i 1; i n; i) { cin a[i]; sum a[i]; maxv max(maxv, a[i]); } ll l maxv, r sum, ans sum; while (l r) { ll mid l (r - l) / 2; if (check(mid)) { ans mid; r mid - 1; // 找最小可行值 } else { l mid 1; } } cout ans \n; return 0; }注意代码里check开头我加了一句if (a[i] x) return false。这个判断很容易被漏掉如果某个元素本身比当前猜测的上限还大那无论怎么分组都不可行直接判false。漏掉它在l从0开始枚举时会导致错误答案。关于答案区间我直接把下界设成maxv而不是0上界设成sum而不是1e9。理由是每个元素不能被拆分所以答案不可能小于最大的单个元素所有元素放一组答案不可能大于总和。收紧区间能减少二分次数虽然log2(sum - maxv)和log2(1e9)差不了几次但这样写出来的代码更自洽也更不容易给check留坑。如果题目要求的是找最大可行值只需要把main里的更新稍微改一下if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; }。其余不动。这就是第二套模板的灵活性。5.2 对拍是二分题最快的调试方式二分题有个恶心人的特点你觉得自己写的没问题样例也过了结果交上去WA到怀疑人生。这种时候别硬瞪眼直接上对拍。对拍的意思是写一个暴力程序枚举所有可能的答案找到正确答案再写一个随机数据生成器最后让暴力程序和你的优化程序跑同一批随机数据比较输出。暴力程序长这样还是按照分组那道题// brute.cpp for (ll x maxv; x sum; x) { if (check(x)) { cout x \n; return 0; } } cout sum \n;随机数据生成器用Python写很方便import random n random.randint(1, 10) m random.randint(1, n) print(n, m) for i in range(n): print(random.randint(1, 20), end ) print()再用一个bash脚本无限循环对拍#!/bin/bash while true; do python3 gen.py input.txt ./brute input.txt ans_brute.txt ./solution input.txt ans_sol.txt if ! diff -q ans_brute.txt ans_sol.txt /dev/null; then echo WA found break fi echo ok done对拍能抓出哪些问题太多了。我自己的一个真实经历是check里cnt的初始值写成了0而不是1导致所有最少分段数都被少算了一段小数据全错但样例恰好避开了Alice。对拍一分钟就暴露了。另一个常见问题是数组下标和边界有的题目输入从1开始读但二分区间和check访问时混用了0基下标。这些东西人眼很难看穿暴力程序一对比马上露馅。建议二分答案题写完以后哪怕时间再紧也要花两分钟跑一轮小数据对拍。5.3 超时真的不是二分的锅如果提交后是TLE先别急着怀疑二分本身。二分次数就是那固定的30次不可能因为数据变大而增多除非你把实数二分写成死循环。更多时候超时是因为check函数内部复杂度爆炸。排查顺序我建议这样来第一步检查check里有没有每次二分都要重新计算的预处理比如每次都对整个数组排序第二步检查有没有在循环内使用vector按值传递而不是按引用导致每次调用check都拷贝一遍大容器第三步检查当前复杂度是否符合前面4.2的表格——如果n是1e5而check是O(n^2)怎么优化边界都是白搭必须换思路。另外一个小坑是输入输出流速度。竞赛里cin不关同步数据一大就会卡这是老生常谈。我统一用ios::sync_with_stdio(false); cin.tie(nullptr);或者干脆用scanf/printf/read模板。二分题本身对常数没那么敏感但叠加在30次check上还是能节省一些时间的。6. 别止步于模板二分查找还能这样延展把P8088这类题吃透之后你其实已经掌握了一个相当通用的思想武器。这个思想还能继续延伸到很多看起来不像是二分的题目上。最后聊聊我自己的延展心得。6.1 实数二分与精度陷阱有些题目的答案是实数比如最大的长度最短的时间就不能再用while (l r)了因为浮点数永远相减不等于0。常见做法两种一种是固定循环次数比如for (int i 0; i 100; i)每轮mid (l r) / 2根据check结果缩小区间。另一种是while (r - l eps)其中eps取1e-7到1e-10。我更推荐固定100次迭代。原因很简单浮点二分的精度是由迭代次数决定的而不是由eps决定的。固定100次区间长度从初始值缩小到2^-100倍什么误差都够用了而且完全不用担心死循环。如果用eps取值太小可能循环太多甚至卡住取值太大又可能导致答案精度不足。实际做题时如果题目要求四舍五入保留三位小数我会设eps 1e-7保留六位就设1e-10或者干脆固定100次。不要把eps设到1e-15这种级别没意义还可能因为浮点误差导致循环不收敛。经验值是比题目要求的精度多两位以上就够了。6.2 用二分思想重看三分与倍增二分思想的一个近亲是三分查找用来求单峰函数的极值。原理是每次取两个中间点比较哪个点更接近极值从而丢掉1/3区间。它在原理上跟二分不同——二分的依据是单调性三分的依据是凹凸性——但那种用少量猜测值排除大段区间的核心思想一脉相承。另一个更常见的亲戚是倍增。倍增本质上可以理解成从高位到低位的二分从大步长开始试可行就累加不可行就缩小步长。经典的应用包括快速幂、跳表、倍增LCA。你会发现这些算法的代码里都有if (满足条件) { 执行跳跃 }这种结构跟二分答案里的if (check(mid)) { l mid; }异曲同工。甚至很多数据结构题里的离线整体二分、树套树的二分套树状数组都是在二分答案思想上长出来的变体。你越往后学越会发现二分不是一个孤立的算法而是一种底层的问题拆分策略。6.3 做题时先把模型写清楚再动手敲代码最后分享一个我自己的做题习惯。每拿到一道疑似二分答案的题我先不写代码先在草稿本上写三行东西第一行答案范围答案是一个整数还是实数最小可能是什么最大可能是什么第二行单调方向答案变大可行性变化还是变坏第三行check模型固定一个x之后问题简化成什么用贪心、模拟、前缀和还是计数这三行写清楚二分题就算解完一大半了剩下的只是翻译成代码。如果第一行就写不出来说明题目根本不是二分答案别硬套。第二行写不出来说明check的单调性没成立需要换建模方式。第三行写不出来说明你对这个题面的基础算法还不够熟先去补充前置知识。我见过太多人题目一拿到手就开始敲int l 0, r 1e9;然后发现mid到底应该往左还是往右完全没想清楚最后在调试器里耗两小时。这真的不是二分难而是步骤没走对。做题和做事一样先想清楚为什么能二分、朝着哪个方向二分再去管模板怎么写效率和正确率都会高很多。这道P8088在我当时做完之后给我留下最深印象的不是它本身有多难而是它让我把不过脑子的模板彻底淘汰掉了。二分查找这种东西代码永远是那几行拼的是一个选手对问题本质的提炼能力。你把这个能力练起来以后遇到任何求某个边界值的题目都会觉得工具箱里多了一把趁手的家伙。