很多刚接触算法竞赛的朋友一听到“二分查找”这四个字脑子里浮现的往往是“在一个有序数组里找一个数”的模板题。但真上了考场二分查找出场的方式远比这个丰富得多尤其是当它化身为“二分答案”的时候整道题的难度和思维量会瞬间上一个台阶。P8088 『JROI-5』Autumn 这道普及的题就是非常典型的一例代码量不大适合二分查找算法的核心技巧但第一眼看上去就像一道纯模拟题稍不注意就会在“模拟每一天”的思路上越走越远最后在超时边缘痛苦挣扎。这篇文章我会把这题从读题、建模、二分答案的设计、边界处理到最终的AC代码一条龙拆开讲清楚。同时把我在实际做题过程中踩过的坑、总结的模板、以及调试二分问题的通用套路全部放出来不管你是刚开始刷普及组题的新手还是已经准备进阶提高组的朋友应该都能从中拿到一些能直接用的东西。1. 题目拿到手先别急着敲代码1.1 P8088 到底考什么从“线性扫”到“二分跳”先说结论这道题的核心考点就是二分查找更准确地说是二分答案。题目背景我印象里是围绕一片果园或者农庄展开的大概意思是给出若干棵树或者若干组生产数据每棵树/每组设备每天产生的资源量各不相同有些还有生产周期、隔天产出的设定现在给定一个目标值M问你最早在哪一天累计产量能达到或者超过这个M。题目本身读起来非常像一个“日子一天一天过、产量一天一天加”的模拟题。如果n特别小、天数上限也不大那暴力循环确实能做。但普及的题不会给你这种甜头数据范围里天数上限通常给到 10^15 甚至更高n也在 10^5 级别。你如果老老实实从第1天模拟到第10^15天哪怕内部只用O(n)遍历一次那也是 10^20 操作量级跑一千年都跑不完。所以这道题真正的第一个思维坎是你能不能意识到我们需要找的不是“模拟到哪一天”而是“答案在哪一天”。天数和累计产量之间是严格单调递增的关系——天数越大累计产量只会越高或者持平但不会下降。这种单调性一出现二分查找就呼之欲出了在1到上限之间猜一个天数mid用O(n)的方式判断“第mid天能不能达标”然后根据判断结果缩小答案范围。从“线性扫”到“二分跳”这不是一个简单的实现替换而是一种思维模式的转变你不再是让时间流动而是主动跳到某一个时间点上去观察状态。这个观察行为本身只需要O(n)的成本但因为你用了二分把观察次数压缩到了 log 级别整个复杂度就从 O(n * T) 降到了 O(n * log T)。这一降直接决定你能不能拿满分。1.2 难度“普及”意味着什么看起来是暴力其实是思维题很多人看到难度标签是“普及”会下意识觉得这题应该是一个“模板题一点点小变形”。但我个人的看法是“普及”这个档位恰恰是区分“背过模板”和“真会做题”的分水岭。模板题是什么给你一个有序数组和一个target叫你写二分查找那叫背板子只要会调库或者能默写三种模板之一分就到手了。而 Autum 这种题它不会在标题里写“请用二分查找”它藏在题面里的是一堆业务条件每天产多少、隔几天集中消耗一次、仓库容量有上限、产量达标之后才计入统计……你需要在读题之后自己看出来“这个问题其实是在一个单调函数上做搜索”并且自己亲手把check函数写对。我当时第一次看这道题脑子里第一个念头也是模拟。毕竟数据量看着不大n才1e5结果一看到天数上限瞬间清醒。然后我就开始在草稿纸上画时间轴怎么把一棵树的产量用函数表示出来怎么把多棵树的产量合并成“第mid天的总产量”。等我把这些数学表达式写清楚二分答案的第一个判断条件已经满足了存在一个单调的评估函数f(x)并且f(x)的真假可以快速计算。这里也顺便说一句很多新手在做二分题目的时候喜欢直接套模板然后把注意力全部放在mid怎么取、while怎么写上面。但真正决定这道题能不能AC的永远是你有没有把题目条件成功翻译成一个“单调布尔函数”。翻译对了模板怎么选都行翻译错了模板再标准也是白搭。1.3 从关键词看题目二分查找在竞赛题里的三种出场姿势聊到“二分查找”这个关键词大家在网上搜到的资料尤其是C语言版本、PTA函数的那些练习绝大多数讲的是最基础的“在有序数组里二分找一个数”。但竞赛中的二分查找至少有三种完全不同的形态你如果不把它们区分清楚看到P8088这种题就容易懵。第一种是最常见的二分查找就是在一个排序好的数组里面找一个值或者找边界典型工具是C里的 lower_bound / upper_bound以及自己手写的标准二分。第二种是二分答案也就是Autumn这道题用到的方式答案不是一个数组中现成的元素而是某个整数范围内的一个值你通过不断判断“当前值是否满足条件”来逼近真实答案。第三种则是更进阶的二分套二分通常用于带权逆序对、二维数点等题目里外面二分答案里面用树状数组或线段树查数量。对于做普及题目阶段的选手来说第二种形态是性价比最高、也最需要练熟的。因为很多所谓的“二分查找题”本质上都是二分答案题它们不会给你现成的有序数组而是给你一个隐形的、单调的函数关系。你能不能在脑子里补出这个函数才是真正的考点。2. 二分答案的核心套路从单调性到check函数2.1 单调性为什么是二分的前提搞清楚你搜索的到底是什么如果让我一句话说清楚二分答案和普通二分查找的区别我会说普通二分是在数组上找元素二分答案是在函数的定义域上找边界。而函数能在定义域上二分靠的就是单调性。什么叫单调性就是随着x变大check(x)返回的结果只会从“假”变成“真”并且一旦变成真之后后面就永远是“真”。这是二分答案能成立的大前提。比如Autumn这题如果第mid天累计产量达到M了那么第mid1天必然也达到M因为产量只会累计增加不会凭空减少。反过来如果第mid天没达到那mid之前的天也一定达不到。这样整个天数区间就被分为两段左边一段全是“不达标”右边一段全是“达标”我们要找的就是这两段的分界点。这个思想可以类比成在一个很长的走廊里找灯亮起的位置走廊前一半是黑的后一半是亮的你每次站在中间看一眼灯亮没亮就能把搜索范围砍掉一半。但这里的前提是——走廊必须真的是一半黑一半亮如果灯一会儿亮一会儿灭你站在中间看一眼根本判断不了该往左走还是往右走二分就完全失效了。所以每次做二分答案题我建议你做的第一件事不是写代码而是在草稿纸上确认三句话第一我猜的这个变量是什么第二我用来判断好坏的函数是什么第三这个函数是不是单调的。三句话都成立再开始写不迟。我还想多说一句单调性并不要求“严格递增”。比如“第mid天累计产量 M”这个判断连续好多天产量不变达标的那一瞬间之后可能连续几天都维持同样的“真”这完全没问题。二分只要求函数值从不真到真最多翻转一次中间是平台期还是直线上升都不影响正确性。2.2 check函数怎么写比二分模板更容易丢分的地方二分答案题最容易丢分的点其实不在二分本身而在这个check函数。check函数翻译得好不好、边界处理对不对直接决定了你的二分在搜一个什么怪物。拿Autumn这类题来说check(mid)的任务是回答一个问题给定第mid天你能不能算出所有树从第1天到第mid天累计产了多少资源然后跟M比较。你要是真从第1天循环到第mid天那又回到模拟的思路上了复杂度直接从O(n log T)退化成了O(mid log T)。正确的做法是对每一棵树用数学公式直接算出它在mid天里面的总产量O(1)时间算完一棵树整个check就是O(n)。比如某棵树每a天产一次果子每次产b个。那么在第mid天之前它产果的次数就是 floor(mid / a)总产量就是 floor(mid / a) * b。如果题目里设定“第一天就产、每a天产一次”那次数就变成 (mid a - 1) / a 之类的向上取整公式。这里的细节差异一定要读清楚题面否则你算出来的产量早晚会差出一次二分结果自然不对。再极端一点如果题目有“仓库容量上限”累计产量超过上限之后就不再增加了那check函数里还要加一个类似 sum min(sum add, cap) 的截断操作。这些业务逻辑才是这道题真正的灵魂写check的时候一定要把题目的每一个角落都扫一遍确认没有漏掉条件。我自己的习惯是check函数只做一件事根据传入的参数x计算这个状态下是否满足题目的目标条件返回bool值。所有计算过程全部放在这个函数内部完成不要在二分主循环里塞任何其他逻辑。这样写的好处是出bug的时候你可以单独调试check函数用一个样例数据跑一遍看看返回值和预期是否一致。2.3 三种二分模板边界问题一次性理清楚写二分答案最常见的问题永远是边界while里到底写 l r 还是 l rmid到底用 (lr)1 还是 (lr1)1一旦写错就会出现死循环或者答案差1。我在这里把三种常用模板都列出来你可以根据自己习惯选一个然后一直用下去。第一种写法是 l 0, r maxRwhile(l r)然后 mid (l r) 1如果check(mid)成立r mid否则 l mid 1最后输出 r。这是“找第一个满足条件的值”的经典写法适用于check(mid)为真时左边界要向右缩小的场合。第二种写法是 l -1, r maxR 1while(l 1 r)mid (l r) 1如果check(mid)成立r mid否则 l mid最后输出 r。这种写法我愿称之为“最不容易写崩”的版本因为循环终止条件 l1 r 保证了最终 l 和 r 之间只剩一个格子天然不会死循环而且区间两端都开不用反复纠结边界到底包不包含。第三种写法是在有序数组里找特定的target常用 l r 的闭区间写法但它不太适合二分答案因为答案题的区间含义通常不是“数组下标”而是“可行解范围”。我个人在所有二分答案题里都推荐第二种写法也就是左开右开区间写法。原因很简单你不需要在循环体内思考“mid是否要加1、减1”因为 l 永远指向不满足的值r 永远指向满足的值循环退出时 r 就是答案。这个写法我第一次是跟一位学长学的用熟了之后发现自己再也不怕边界问题了强烈建议还没找到顺手模板的朋友试试。3. 实操环节从读题到AC的完整流程记录3.1 数据建模把题面翻译成二分答案的数学表达式现在我们来模拟一次完整的做题过程把Autumn这道题从头到尾梳理一遍。题面细节我按常见的果园题设定来演示有n种生产装置我们就叫它们“树”吧第i棵树有一个生产周期 p_i每次成熟后能收获 c_i 个果子所有树从第1天开始运作目标是让累计产量首次达到M问最早是哪一天。这里有个很关键的点每棵树不是每天都有产出它只在周期结束的那一天一次性产出。这样一来“总产量”不是一个简单的每天累加而是每一棵树在 x 天内的产出次数乘以每次产量再加总。翻译成数学公式就是total(x) Σ (floor(x / p_i) * c_i)然后check(x)就等价于判断 total(x) M 是否成立。你看一旦把这个公式写出来整个题目就从“模拟每天发生了什么”变成“算一个带取整的函数值”了。我们二分的就是这个函数首次超过M的x值。这里还有一个比较容易忽略的点题目问的是“首次达到M的那一天是哪一天”如果第0天就有初始库存那初始库存也要加进去。我们在建模的时候可以单独用一个变量 base 表示初始库存check函数判定的就是 base total(x) M。这种小细节虽然不难但漏掉任何一个都会让你在最简单的样例上就挂掉千万不要觉得样例过了就万事大吉。3.2 AC代码逐行拆解C实现的完整参考下面我把这道题的C完整AC代码写出来然后逐段讲解。不同版本的题面细节可能略有差异但整体框架可以直接套用。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100000 5; int n; ll p[MAXN], c[MAXN]; ll M; ll base; bool check(ll x) { unsigned long long sum base; // 初始库存 for (int i 1; i n; i) { // 第i棵树在x天内的产出次数 ll times x / p[i]; sum (unsigned long long)times * c[i]; if (sum (unsigned long long)M) return true; // 提前退出防溢出 } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n; for (int i 1; i n; i) { cin p[i] c[i]; } cin M base; if (check(1)) { // 特判第1天就达到 cout 1 \n; return 0; } ll l 1, r 1; // 倍增找上界先用翻倍的方式确定一个一定可行的天数 while (!check(r)) { l r; r 1; if (r 0 || r 4e18 / 2) { // 防止越界 r 4e18; break; } } // 二分答案左开右开模板 while (l 1 r) { ll mid (l r) 1; if (check(mid)) r mid; else l mid; } cout r \n; return 0; }这段代码的核心思路是先用倍增的方式快速找到一个足够大的上界 r然后在这个区间内二分。第1天特判是很多人都容易忽略的如果第1天就已经达标了直接输出1就好不需要进二分。如果你不特判l 初始值设为1r 又从1开始翻倍那 check(1) 为真的情况下会空转一轮或者直接输出错误结果非常坑。倍增找上界这个技巧是我做二分答案时特别喜欢用的。你可能想为什么不直接设 r 1e18 然后开二分答案很简单第一你设1e18必须在check里计算天数接近1e18时的总产量这时候 sum 不溢出才怪你得额外处理第二倍增找上界通常可以让 r 停在距离答案比较近的位置这样二分查找的轮数更少代码运行更快。比如真实答案是100万r 经过20次翻倍就到约100万了上下界区间一开始就很紧凑。3.3 long long、上界与溢出的三个大坑这段代码我给 sum 用了 unsigned long long为什么因为题目数据稍微刁钻一点n 取1e5p_i 取1c_i 取1e9M 取1e18那么第1e18天的总产量就是 1e5 * 1e9 * 1e18 1e32早就超出 long long 的范围了。虽然我们不会真的让 sum 累加到那么大才去判断因为check里一旦 sum M 就立刻 return true但当M本身就是1e18的时候sum 在超过1e18的那一刻就会被截断看起来好像没问题。但如果你忘记了提前退出老老实实把 n 个数的产量全部累加完那 sum 就会疯狂溢出结果变成随机数二分完全崩掉。所以这里有三个大坑每个都值得单独说一下。第一中间乘法溢出times * c[i] 这个操作times 和 c[i] 都是 long long乘出来的结果可能超过long long。在累加到sum之前最好的做法是强制转换成 unsigned long long 再乘。第二sum累加溢出虽然提前退出可以缓解但如果不小心某个测试点M特别大、n特别大sum在退出之前已经超过了2^64unsigned long long也会溢出。更稳妥的做法是直接用 __int128 作为sum的类型这是GCC的扩展类型中间运算随便造只要最终结果不超过128位范围就行。第三二分上界r本身溢出r 1 这种倍增操作如果一直翻下去也会溢出所以我在代码里加了 r 4e18 / 2 的判断当作保护。还有一个经常被忽略的点就是“乘除的顺序”。比如你要算 x / p_i * c_i因为 p_i 可能特别大c_i 也可能特别大正确的顺序是“先除后乘”利用整除先缩小数值范围避免不必要的溢出。如果你先乘后除中间结果直接炸掉算出来的东西就完全没意义了。这个习惯对于所有算法题都是通用的尤其是涉及大数的统计题。4. 常见问题与排查技巧实录4.1 死循环、答案差1、超时的三大根源做二分答案题最常见的三个症状无非就是死循环、答案比正确答案大1或小1、运行超时。这三个问题看着完全不同但根源往往集中在几个地方。死循环几乎都是循环条件写错导致的。如果你用 while(l r) 又搭配 mid (l r) 1然后当 check(mid) 为真时写 l mid就会出现当 l 和 r 只差1时mid 等于 lcheck(mid) 为真后 l 还是 l永远死循环。解决办法就是换用 l 1 r 的写法或者保证每次移动的都是某个边界且必变动。答案差1则往往是边界取错了比如你找的是“第一个满足条件”的值结果模板里写成了“最后一个不满足的值1”最后输出时也忘了处理初始边界。超时则通常是check里套了复杂度太高的操作比如每次check都要排序一下、每次check都要重新初始化一个大数组这就把原本 O(n log T) 的复杂度拉爆了。如果你在自己机器上调试时发现这些症状我建议你第一步不是读代码而是先打印中间值。把二分过程中每一次的 l、r、mid、check(mid) 都打出来很快就能看到是循环条件的问题还是check函数的问题。绝大多数情况下边界错误一眼就能在这样输出的过程中被抓到。4.2 对拍器与暴力程序验证check函数正确性的最快方式我一直觉得写二分答案题最强大的调试方式不是人工盯代码而是写一个暴力的小程序去对拍。具体做法特别简单先写一个完全按照题面模拟的暴力版本从第1天循环到答案上限逐天计算产量直到达到M输出这一天。然后写一个随机数据生成器每次生成 n 很小的数据比如 n 5天数上限 100同时喂给暴力程序和二分程序比较两个程序的输出是否一致。只要随机数据量大一点比如跑几千组你的check函数里哪怕藏着一个特别隐蔽的边界 bug也一定会被揪出来。这个方法在竞赛圈里几乎是公开的秘密但我发现很多新手在刷题时完全不知道。有时候代码卡在一个样例上死活过不去如果身边没有题解可看写个暴力对拍往往几分钟就能定位问题。尤其是二分答案这种“错误不会直接爆WA而是会在特定边界上爆出答案差1”的题对拍的价值比任何调试技巧都大。我在Autumn这道题上就是用这个方法发现了我check函数里对“每a天产一次”这个周期的取整写错了——我曾经直接用了 x / p_i忽略了“第1天也会产”这个条件导致所有mid都会被算少一次产量。对拍跑出差异的那一刻我差点拍桌子因为这种逻辑错误靠干瞪眼真的很难发现。4.3 现场翻车实录我在这个题上踩过的三个真实大坑为了让大家少走弯路我把当年在类似题目上实际踩过的坑整理一下。第一个坑是固定上界带来的溢出。我当时嫌倍增找上界麻烦直接用 r 1e18 开二分结果check里有一棵树p_i特别小x特别大times*c[i]直接爆掉导致check判定完全错乱。后来把 r 的寻找方式改成倍增同时乘法用128位承接以后这个问题就再也没出现过。第二个坑是初始库存忽略不计。题面里明明写到“果园已经储备了一批果子”我却想当然地以为初始库存是0结果所有测试点都比正确答案多了好几天。这种教训很简单读题时对条件逐字抠尤其是数字和定语。第三个坑是二分区间左端点设计不合理。我当时上来就用 l 0但check(0) 的逻辑写错了直接报错。后来我把 l 的语义固定为“一定不满足的天数”初始化成0并把check(1)特判做掉整个逻辑就顺了。这三个坑总结出来其实是同一句话二分答案题的代码不难难在把题面的每一个限制条件都完整、准确地塞进check函数里。那些WA在测试点13、14上的同学通常不是二分写错而是check里漏了一个条件。5. 不止为了AC二分查找思想还能用在哪5.1 从竞赛题到日常工作二分查找不止是算法题里的“玩具”说句实话二分查找在工程实践里出现的频率比很多人想象的都要高得多。你写日志系统时要在一大坨按时间排序的日志里找到某一天的第一条错误日志这就是二分。你在性能测试里要找出某个接口在并发量达到多少时开始超时这也构成一个单调关系并发量越大超时越多。你可以用二分逼近那个临界并发数而不是一个一个往上试。我做项目时有一次需要在一个巨大的存储系统里定位数据损坏的最早时间点。这个系统每天会生成一个快照而损坏从某一天开始持续出现。由于快照数量特别大而“是否损坏”的性质又是单调的——之前全好之后全坏——我直接在快照列表上写了个二分定位十几行代码解决问题。当时旁边的同事还在用逐天检查的方式跑脚本过来看到我已经定位完第一反应是“你怎么知道一定是这一天”。我告诉他这不是猜测这是二分查找。这类问题在工程里真的很多你只要看到的场景里满足“前一段是A状态、后一段是B状态、且两段单调变动”的特征脑子里就自动弹出二分的模型会非常省事。所以别把二分查找当成只活在竞赛题库里的技巧。它其实是人类解决问题的一个基本思维模型在未知环境中用最少的尝试次数定位边界。好比你在黑暗中摸一根灯绳你不需要从门口一寸一寸摸过去你只需要每次都跳到剩余长度的中间摸一下就知道灯绳在这半边还是那半边。算法竞赛训练的就是这种在约束下快速定位的直觉。5.2 几个值得一试的进阶变式如果你把Autumn这道题做透了对二分查找产生了兴趣我建议你再尝试几个变式它们的基础思维是一样的但代码细节各有不同。第一个是三分查找用于求一个凹函数或者凸函数的极值点。它和二分答案的区别在于二分答案找真假分界点三分查找找函数峰值每次比较两个mid点然后塞掉一段区间。第二个是二分答案和数据结构结合典型的就是“二分数值 树状数组/线段树计数”用来解决第k小、逆序对数量限制等问题。第三个是lower_bound/upper_bound的高阶使用比如在多重集的场景下找某个区间内有多少个数落在[L,R]范围内可以在排序后的数组上先lower_bound(L)再upper_bound(R)两个迭代器一减就是答案。这种组合我几乎每周都在用。我个人经验是比起死记硬背各种模板不如先把“单调函数的真假分界”这个思维模型打磨透彻。Autumn这道题的价值不在于让你会做一道果园题而在于让你以后看到任何“最早、最晚、最短、最少”的表述时大脑自动开始思考这个变量是否单调能不能二分有了这个条件反射你刷再多的二分题目都不会觉得白费因为它们只是在反复强化同一种思维方式而已。