P8088『JROI-5』Autumn难度普及标签里简简单单四个字二分查找。第一次看到这道题的人多半觉得这就是一道套模板的水题。但带过几年算法竞赛我就明白凡是在“普及”这个档位被反复讨论的二分题真正考的都不仅仅是模板本身——它考的是你什么时候能意识到“答案本身可以被二分”。这篇文章就以这道题为主线把二分查找从经典模板讲到二分答案从C语言实现讲到PTA函数题里那些容易挂分的细节。无论你在准备CSP-J/S、蓝桥杯还是被学校PTA作业折磨这套思路都通用。我会把边界处理、mid取值、check函数设计、死循环排查这些我实际踩过的坑全部摊开讲最后再给一个可以直接抄作业的完整代码。1. 题目与背景一道普及的二分题为什么值得反复做1.1 从标题信息里能读出什么先拆一下标题。“P8088”说明这是洛谷题库的题号“JROI-5”指向某个社区赛事的第五场比赛“Autumn”是题目名末尾的“普及”是难度评级搜索关键词“二分查找”直接点明了正解方向。社区赛的题有一个共同特点题面通常不短但正解往往很朴素不会上来就甩你一棵线段树。这种题最考察的就是“把生活化的场景翻译成算法模型”的能力而Autumn这种名字基本暗示了题目里会有一个随时间或者随位置变化的过程比如日照时间、气温曲线、叶子飘落的位置然后让你在某个变量上求最大值或最小值。难度定在“普及”意味着它比纯普及组的模拟题多了一点思维量但还不到提高组那种需要数据结构加持的程度。这种题最舒服的解法就是二分答案加check函数。你不需要维护复杂的数据结构只需要回答“如果某个值是这个数行不行”然后用二分把最优值找出来。这也是我特别喜欢拿这类题给刚学完排序和枚举的选手练手的原因。1.2 二分查找在竞赛技能树里的位置二分查找是算法竞赛里性价比极高的一项技能。学会它只需要半小时真正掌握它可能需要几十道题但它能撬动的题目范围非常大从有序数组里找数字、从旋转数组里找最小值、求最大值最小化、最小值最大化、实数域上的精度逼近甚至是对着单调函数求零点全部是二分的地盘。在C语言的支持下二分查找的代码量并不大但它对思维习惯的要求很独特。你需要习惯“通过不断缩小答案的可能范围来逼近真实答案”而不是“一步一步枚举出答案”。很多新手第一次写二分总忍不住在循环里打印一坨调试信息然后发现死循环了这就是因为脑子里还残留着枚举的思维惯性。等你真正把“区间收缩”这个思想焊死在脑子里再看P8088这种题一眼就能分辨出它是不是二分答案题目要你求一个最值而且这个最值的可行性随答案单调变化那就二分。2. 二分查找的根从有序数组定位到“猜答案”2.1 经典二分查找的写法与不变量不管是什么花样的二分底层都是那个最经典的问题在一个有序数组里找一个数。C语言实现通常长这样int binary_search(int a[], int n, int x) { int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] x) return mid; else if (a[mid] x) l mid 1; else r mid - 1; } return -1; }这段代码的关键不是那三行if而是理解循环里始终维持的不变量答案如果存在一定在区间[l, r]里。所以每次比较a[mid]和x之后我们可以放心地丢掉一半区间因为丢掉的这一半里绝对没有答案。这个不变量是二分的灵魂后面所有边界处理都是为了保证它不失效。很多人问为什么不用mid (l r) / 2而要用l (r - l) / 2。在纯竞赛环境里可能无所谓但在工程或PTA的测试数据里l r可能溢出int这是真实存在的问题。养成用减法计算mid的习惯能省掉一次崩溃。这个细节我不会再强调了反正后面每一段代码都按这个习惯写。2.2 三种区间写法与边界翻车点二分查找的写法不止一种关键是选一种你永远能记住的然后每次都用它。我把三种常见的区间写法整理成了一张对照表写法区间形式循环条件mid调整方向适用场景闭区间[l, r]l rl mid 1 / r mid - 1精确查找某个值左闭右开[l, r)l rl mid 1 / r mid找第一个满足条件的位置开区间(l, r)l 1 rl mid / r mid实数二分或特殊边界题闭区间写法最容易理解但处理“找第一个大于等于x的数”这种问题时左闭右开写法更不容易出错。原因在于r mid这个操作不会跳过答案而r mid - 1一旦在mid等于答案时执行答案就被丢出区间了。举个实际翻车例子。有人用闭区间写lower_bound写成下面这样int lower_bound_bad(int a[], int n, int x) { int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid - 1; else l mid 1; } return l; }这段代码在a[mid]恰好等于x时把r收缩到mid - 1最终返回的l确实可能是第一个等于x的位置但处理大量重复元素时极其容易绕晕。我用左闭右开模板很多年很少在这种细节上翻车。所以在下面的内容里除非明确说要精确查找某个值不然统一用左闭右开。2.3 lower_bound与upper_bound的C语言实现竞赛里的二分查找更多是配合排序解决“某个值出现几次”这类问题。C语言标准库虽然提供了bsearch但它返回的是任意一个匹配位置没法直接满足“统计重复次数”的需求。所以手写lower_bound和upper_bound是必备技能int lower_bound(int a[], int n, int x) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid; else l mid 1; } return l; } int upper_bound(int a[], int n, int x) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid; else l mid 1; } return l; }于是数字x在有序数组里的出现次数就是upper_bound(a, n, x) - lower_bound(a, n, x)。这里有个非常容易忽略的坑lower_bound的返回值可能等于n表示x比整个数组都大upper_bound也可能返回n表示所有数都小于等于x。如果你拿这个返回值直接去当数组下标必越界。我早年写统计词频的程序时就因为没判断返回n的情况在PTA上反复爆运行时错误后来养成了拿到返回值先看是否合法的习惯。3. 二分答案把最优问题转化为判定问题3.1 什么时候能二分答案P8088这种题真正的核心不是二分查找数字而是二分答案。二分答案解决的是一类看起来和“查找”无关的问题题目要你求一个最优值比如最小花费、最大距离、最短时间而且这个最优值的可行性随着答案的变化是单调的——答案越大越有可能满足条件或者反过来答案越小越有可能满足条件。用生活例子理解你女朋友让你在预算内买礼物预算越高买得到满意礼物的可能性越大。如果我想知道“花多少钱才能让她满意”我不用从一块钱开始慢慢试我可以直接猜一个中位数她说不够我就往高价猜她说太多我就往低价猜。这个“往哪边猜”的依据就是单调性。放到算法题里单调性通常表现为设f(x)为“当答案限制为x时能否完成目标”那么f(x)必须是一个单调函数。如果x增大f(x)从false变成true说明答案越小越难这叫最小值最大化问题反过来如果x增大f(x)从true变成false说明答案越大越难这叫最大值最小化问题。看到题目里的“使最大值最小”或“使最小值最大”直接往二分答案上想基本不会错。3.2 check函数的设计套路二分答案最关键的部分是check(x)函数它决定整个算法能不能跑对。check的任务是回答一个问题在答案限制为x的情况下方案是否存在。这个函数通常用贪心或模拟实现复杂度最好是O(n)或O(n log n)因为二分答案会在外层做log V次V是答案值域check每慢一点总时间都会被放大几十倍。设计check的核心技巧是“往前看”从左到右扫描能安排就安排不能安排就换新的一段。比如经典题“把n个数分成m段每段和不超过x”check就直接累加超了就开新段最后看段数是否小于等于m。这种做法能保证在x的限制下段数是最少的所以如果最少的段数都超出mx一定不可行。很多新手写check时总想把方案也求出来比如不仅判断能不能还想知道具体怎么分。这个思路在二分答案里是多余的你只需要回答“能不能”具体方案留给原题需要的时候再说。把check写成一个干脆利落、只说“行还是不行”的函数是二分答案题拿高分的秘诀。3.3 最大值最小化与最小值最大化的代码模板我把两个方向的二分答案模板都整理出来。第一个是“最大值最小化”比如把一些工作分配出去求最大耗时最小能到多少int l 0, r 1e9, ans 0; while (l r) { int mid l (r - l) / 2; if (check(mid)) { ans mid; r mid - 1; // 当前可行继续尝试更小的值 } else { l mid 1; // 不行只能增大限制 } }第二个是“最小值最大化”比如在坐标轴上选k个点让点与点之间最小距离尽量大int l 0, r 1e9, ans 0; while (l r) { int mid l (r - l) / 2; if (check(mid)) { ans mid; l mid 1; // 当前可行尝试更大的值 } else { r mid - 1; } }这两个模板唯一的差别就是可行时往哪个方向收缩。很多人在考场上背混然后对着数据发呆。我的办法是每次都在注释里写清楚“ans记录的是最后一个可行的值”然后只记住一句话能让答案继续变优的方向一定是可行时移动的方向。4. P8088题解思路推演与实战演示4.1 没有完整题面时怎么用标签反推套路实话说具体到P8088的原始题面我不保证每一个细节都能一字不差复述出来。但这类社区赛题目有一个共性题面给你一个具体场景然后让你求一个最值标签里的“二分查找”几乎在明示你应该用二分答案。拿到题先别急着看数据范围先问自己三个问题题目要求的最优值是什么这个最优值变大时条件会更容易还是更难满足check函数能不能用一遍扫描判断把这三个问题想清楚就算原题描述再花哨骨架也已经出来了。Autumn这个主题在算法题里最常见的包装是一个序列上的值随时间递增或递减然后让你找一个分界点左边满足某个性质右边不满足。这个分界点本身就是二分的对象。4.2 一个Autumn风格的典型模型落叶清扫问题为了把二分答案讲透我现场构造一个与Autumn气质相符的模型题。剧情是一条长度为L的路上飘落了n片叶子第i片叶子落在坐标a[i]处。清洁工从0出发每趟可以清扫一段长度不超过x的连续区间扫完一趟必须回0倒掉叶子。现在规定最多只能扫k趟问清扫长度x至少要设置为多少。这个问题要你求最小可行的x属于最大值最小化因为x越小越难完成x越大越容易。单调性很明显x增大每趟能覆盖的范围变大总趟数不会变多。check(x)的思路是把叶子坐标排序后从第一片没扫的叶子开始每次从它所在位置往右覆盖长度x这一趟就能扫掉区间内所有叶子统计趟数最后判断趟数是否小于等于k。这里有个小细节叶子坐标必须先排序因为清扫区间天然要求坐标有序题目给出的a[i]可能是乱序的。排序之后贪心覆盖才能保证趟数最少。如果直接拿原序扫描check出来的趟数可能是错的甚至可能导致合法的x被误判成非法。4.3 完整C语言实现与手算演示下面给出这个落叶清扫模型的完整实现代码可以直接改改用于P8088这类二分答案题#include stdio.h #include stdlib.h int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int n, k; int a[100005]; // 判断当每趟清扫长度为x时能否在k趟之内扫完 int check(int x) { int cnt 0; int i 0; while (i n) { cnt; int cover_end a[i] x; while (i n a[i] cover_end) i; if (cnt k) return 0; } return 1; } int main() { int L; scanf(%d%d%d, n, k, L); for (int i 0; i n; i) scanf(%d, a[i]); qsort(a, n, sizeof(int), cmp); int l 1, r L, ans L; while (l r) { int mid l (r - l) / 2; if (check(mid)) { ans mid; r mid - 1; } else { l mid 1; } } printf(%d\n, ans); return 0; }我用手算模拟一遍加深理解。假设叶子坐标是1、4、7、12、20n5k3。先看mid可能取到9从1开始清覆盖到10所以前三个叶子1、4、7一趟清掉下一趟从12开始覆盖到21把12和20都清掉。总共2趟小于等于3可行。于是收缩r尝试更小的x。再看x6第一趟1覆盖到7清掉1、4、7第二趟从12覆盖到18清掉12第三趟从20覆盖到26清掉20。正好3趟可行。继续缩小。x5时第一趟1覆盖到6清掉1、4第二趟从7覆盖到12清掉7、12第三趟从20覆盖到25清掉20。正好3趟也可行。那x4呢第一趟清1、4第二趟清7第三趟清12第四趟清204趟超了不可行。所以最小x就是5。通过这个手算过程你能直观看到二分答案并不是什么高深技巧它就是把这个“从4不行到5可行”的分界点找出来。P8088无论场景换成温度还是距离底层逻辑都是这一套排序、贪心check、二分边界。5. 从竞赛到平台PTA函数题与工程化写法5.1 PTA二分查找函数题的经典模板很多读者搜“二分查找pta函数”是因为学校布置了PTA上的函数题。这类题的经典形式是给你一个有序链表结构体或者数组结构体让你实现一个BinarySearch函数接口看起来像这样Position BinarySearch(List L, ElementType X)其中List是一个结构体指针结构体里存着Data数组和Last变量Last表示数组最后一个元素的下标。这道题的本质和一个裸数组二分没有区别但有两个坑第一题目为了统一接口Data数组下标从1开始Last存的是最后一个元素的位置所以右边界是L-Last而不是L-Last - 1第二查找失败时需要返回一个约定的NotFound宏通常定义为0。一个适配这种接口的标准写法如下Position BinarySearch(List L, ElementType X) { int l 1, r L-Last; while (l r) { int mid l (r - l) / 2; if (L-Data[mid] X) return mid; else if (L-Data[mid] X) l mid 1; else r mid - 1; } return NotFound; }很多人在这个函数题上挂分不是因为二分不会写而是没看明白接口约定到底下标从0还是从1开始。我的建议是写函数前先确认Last的含义如果题目说“Last表示最后一个元素的位置”大概率下标从1开始。PTA的判题比较死板错了不会告诉你具体数据所以这种边界细节必须靠自己抠清楚。5.2 手写二分与标准库的取舍工程实践中C语言标准库提供了bsearch函数配合qsort使用可以做二分查找。但bsearch有两个问题它只返回任意一个匹配位置无法直接处理“统计重复元素个数”的需求其次bsearch的比较函数签名比较繁琐对新手不友好。所以手写lower_bound和upper_bound在面试和竞赛中依然是硬技能。C选手可以直接用STL里的binary_search、lower_bound、upper_bound但在C语言环境下手写是唯一选择。我建议你把第2小节的三个函数背到肌肉记忆binary_search、lower_bound、upper_bound。这仨在打比赛时就是你的左膀右臂连键盘都不用看就能敲出来。5.3 二分查找的复杂度分析与实际耗时二分查找单次的时间复杂度是O(log n)。之所以快是因为每次比较都能排除一半的候选区间。从4096个数里找一个数最坏也只需要12次比较这个效率是线性查找完全没法比的。二分答案的复杂度要乘以check的复杂度O(log V)次二分乘上每次O(n)的check就是O(n log V)其中V是答案的值域。如果题目给的坐标范围是10^9log V大约是30再乘n等于100000的话大概300万次运算在1秒时限内非常轻松。这也是为什么普及难度的二分答案题不需要优化check到O(log n)O(n)的check已经足够快了。6. 常见问题与排查实录6.1 死循环mid的取整方向惹的祸二分题死循环是新手最常遇到的现象典型症状是程序卡在那里不结束。最常见的病根是左边界的更新方式写成了l mid配合mid (l r) / 2向下取整时如果l和r只差1mid就会等于l更新后l还是原来那个值区间不收缩循环永远跑不完。解决死循环的办法有几个。第一个办法是在纸上模拟区间只有两个元素时的情况比如l5, r6看看这一轮操作后区间能不能缩小。第二个办法是把循环条件改成l r而不是l r配合左闭右开区间记忆负担会小很多。第三个办法是在循环里加一个计数器超过100次直接终止调试阶段用这个办法能快速定位问题。6.2 边界错误mid - 1和mid 1谁该用边界更新错误是二分题另一大类bug。很多人不敢在收缩区间时加减1怕把答案漏掉结果写成了l mid或者r mid导致死循环或者答案不对。其实只要你维护好了“答案永远在[l, r]区间内”这个不变量该加1就加1该减1就减1完全不用担心漏答案。我排列一个速查表场景可行时更新不可行时更新最大值最小化r mid - 1l mid 1最小值最大化l mid 1r mid - 1精确查找l mid 1 / r mid - 1无这个表配合ans变量能解决绝大多数边界问题。核心原则是mid已经判断过了它不可能再是下一步的候选答案所以更新时一定要让mid退出区间。6.3 check函数不单调二分直接失效如果check函数本身不满足单调性二分答案就是空中楼阁。比如某些题的条件是“x必须恰好等于某个数”这时候check(mid)的结果可能是true、false、true交替出现二分完全没法收敛。遇到这种情况要警惕题目其实不是二分答案而是别的算法比如前缀和加哈希或者数学推导。一个小技巧是写check之前先用小数据把x从小到大都测一遍打印出check(x)的true/false变化序列。如果这个序列是连续的true之后接连续的false或者反过来二分才能成立。这一步只要花一分钟能省掉改半天代码的时间。6.4 调试技巧对拍、打印区间、极限数据调试二分题我最常用的三招。第一招是打印区间在循环开头打印l、r、mid看一眼区间收缩的方向对不对几个数就能看出问题。第二招是对拍写一个纯暴力的枚举解法然后在n很小的时候跟二分做法对比结果。第三招是极限数据把答案推到题目允许的极小值和极大值确认check在边界情况下不会越界、不会除零、不会溢出。这三个方法看起来土但比冥想管用一百倍。我平时给学生讲题一律要求他们先打暴力再写正解两道代码对上了才提交。二分题尤其适合这种流程因为它的逻辑容易在细节上出错而对拍能自动暴露这些错误。我个人的体会是二分查找本身不是难点难点永远是“敢不敢把最优问题交给一个不直接求答案的算法”。很多选手第一次接触二分答案会有一种“我都没算出方案这答案怎么就出来了”的别扭感。这种别扭是正常的多刷几道题就顺了。如果你正卡在P8088这种普及的二分题上照着这篇文章的步骤走找单调变量、写check、套模板、对拍验证。做完这四步你收获的不只是一道题的AC而是一整套处理“求最值”问题的方法论。