我在题库里刷题的时候遇到过这么一道：题号P8088，题目叫『JROI-5』Autumn，难度标的是普及+，算法标签就四个字：二分查找。当时第一反应是：二分查找嘛，代码二三十行的东西，无非是while套mid，几分钟就能AC。结果真正上手之后才发现，问题根本不在二分本身，而在于你能不能把一个看似复杂的判定问题，压缩成一个单调的check函数。

这些年我有个越来越强烈的感受：普及+这个难度段，二分题是最容易拉开差距的。模板谁都会背，但题目一变，很多人就认不出"这是二分"了。今天借着P8088这道题，我不打算复述原题面——网上搜一下就能看到——而是想把这套我从大量二分题里提炼出来的完整解题框架讲透。从二分的三种出题模型，到边界处理的死循环问题，再到check函数怎么写、复杂度怎么预算、对拍怎么调，一次性讲清楚。这篇内容不挑具体语言，示例代码我用C++写，但思路换到Python、Java一样通用。

如果你正在备赛，或者刚刷完一批二分模板题但碰到新题还是发懵，这篇文章应该能帮你把"背模板"升级成"建模型"。

1. 从P8088说起：一道普及+二分题暴露出的算法盲区

先聊聊我为什么对这道题印象这么深。我当时是在一次集中的二分专题训练里遇到它的，那次训练一共十道题，从红题一路刷到提高+，P8088正好卡在中间偏前的位置。按我最初的想法，这种题五分钟内应该能拿下，结果我在边界和check的设计上反复折腾了一个多小时，最后不得不打开题解才确认了自己的方向没问题，只是实现细节抠得太粗糙。

这种体验我相信很多人都有过。你问一个学过算法的人"会不会二分查找"，他多半会说会；但你要是给他一道没有明确"有序数组"字样的题，让他自己发现该用二分，他就卡住了。这说明什么？说明大家背的是模板，缺的是模型。

1.1 为什么这道题会成为分水岭

普及+题目的典型特点是：算法标签很直白，但题面会给你绕弯子。P8088的标签写着二分查找，可它真正想考察的不是"在数组里找个数"这种基础操作，而是"你能不能看出来答案可以二分"。

这里有个很现实的差距：基础扎实的人看到题，先想答案的值域，再想check函数好不好写，最后才决定要不要用二分；只会背模板的人看到题，满脑子都是"mid = (l + r) / 2""while(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可行。

这个检查函数，就是我们要写的check：

bool 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^2，n到1e5直接起飞；check是O(n log n)，那总复杂度30n log n，n在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还是3，r还是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复杂度和数据范围匹配起来。下面这张表是我做题时心里默算的参考：

所以你看到一道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. 从通读到AC：P8088的实战复盘与完整代码骨架

理论讲完，进入实际操作。这里我给出一份我能稳定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在我当时做完之后，给我留下最深印象的不是它本身有多难，而是它让我把"不过脑子的模板"彻底淘汰掉了。二分查找这种东西，代码永远是那几行，拼的是一个选手对问题本质的提炼能力。你把这个能力练起来，以后遇到任何"求某个边界值"的题目，都会觉得工具箱里多了一把趁手的家伙。