计蒜客的二分查找系列做到第五题很多人才开始真正体会到一个道理二分查的从来不只是数组它查的是答案。T1555 的题面不会给你一个排好序的数组让你找一个 target它给你的是另一类东西——一组初始数据、一个需求描述、一个要最大化或最小化的目标值。前四道题把“在有序序列上定位元素”的基本功练扎实了到这一题才轮到检验你懂不懂二分的本质在一条只有 true 和 false 的判定序列上找到那个分界点。这篇题解写给三类人刚背熟二分模板、但对边界条件一知半解的初学者在在线评测平台上反复提交、被超时和答案错误折磨的刷题人以及想系统掌握“二分答案”这个进阶套路、准备笔试面试的选手。接下来我会从题目拆解、模板选型、完整可 AC 的代码、再到四个隐蔽 bug 的排查思路把 T1555 以及它背后的一整类问题讲透保证你读完能直接复现下次遇到同类题也有清晰的入手点。1. T1555 到底考什么从“数组里找值”变成“值域上猜答案”1.1 五道系列题的难度是怎么层层递进的先把这条题单的前四题放一起看。第一题基本是给一个有序数组判断某个值在不在里面这是最标准的二分模板练习第二题开始考重复元素下的左边界和右边界你会发现判断条件从“等于 target”变成了“大于等于 target”第三题往往是 lower_bound 和 upper_bound 的变体要求你找出插入位置本质还是边界问题第四题很多人就开始卡了因为数组不再规规矩矩给你可能是旋转数组也可能变成二维矩阵。到第四题为止二分查找的下标始终是数组下标判定函数始终是 a[mid] 和 target 的比较背模板基本能混过去。到了第五题套路就换了。没有数组供你二分只有一个值域范围和一个可写的判定函数 check。你要做的不是在数组里找位置而是在答案的取值空间里“猜答案”猜一个值 x用 check(x) 判断它合不合理然后根据结果把搜索区间砍半。这就是常见的二分答案套路。前四题练熟的人走到这里最容易被惯性坑到——看到题先想排序、枚举、双指针完全没想到答案本身才是二分对象。如果你也有这种“看到题先排个序”的冲动说明你还没从下标二分切换到值域二分这个思维模式上T1555 正好是帮你完成这次切换的关键一题。1.2 题面里有三句话决定了你能不能写出 check以这类题最常见的切绳子版本为例题面大意是给 n 根长度不等的绳子要求切出至少 m 段长度完全相同的绳子问每段最长能是多少。很多同学读这种题只盯着样例数据把三句最关键的信息划过去了。第一句是“求什么”这题要的是每段绳子的最大长度这个量就是二分对象第二句是“判定条件”至少 m 段这是 check 函数要返回的布尔值第三句是“输出要求”如果做不到 m 段应该输出 0这直接决定你的二分左边界初始值。这三句话对应的信息量分别决定二分对象的取值范围、check 怎么写、以及 l 和 r 的初值。哪怕题面换成切木材、分糖果、划分数列只要这三条信息能对上问题的数学模型就是同一个。我见过很多人读题只花三十秒样例看懂了就开写结果写完发现 check 里不知道该返回什么、边界初值不知道该取多少。建议养成习惯动笔前用一句话把题面压缩成“求什么、判什么、边界怎么输出”这句话写出来代码结构基本就定了。1.3 单调性是二分的大前提必须先证明再写代码很多题解上来就给模板好像二分天生就该这么写。但 T1555 这类题能二分的唯一原因是可行性随答案呈单调变化。用切绳子举例如果每段长度定为 4 米能切出至少 m 段那么每段长度定为 3 米一定能切出至少 m 段因为你只会切得更碎、段数只会更多反过来如果 4 米切不出 m 段5 米更不可能。所以 check(x) 的取值序列一定是若干个 true 后面接若干个 false永远不会出现 true、false、true 的反复横跳。有了这条单调性二分才能成立找到最后一个 true 的位置就是要求的最大可行长度。写代码前花三十秒把这个逻辑在草稿纸上推一遍能帮你避免大量无效调试。我的习惯是先在代码注释里写一句话——“若 check(mid) 为 true则所有更小的值都为 true”确认这句话成立再动笔写循环。很多人忽略这一步直接在 check 里写一堆复杂的判定逻辑结果二分出来的答案莫名其妙怎么查都查不出问题最后才发现是判定函数本身不单调。2. 二分模板这么选左闭右开写法为什么更不容易翻车2.1 两套整数模板的对比二分答案题里我们找的是“最后一个可行的值”这和数组里“找一个精确值”的模板有一个微妙的差别当 check(mid) 为 true 时我们不能直接返回 mid因为右边可能还有更大的可行值此时必须 l mid把下界往上抬。这个“成立时保留 mid”的写法是所有死循环 bug 的源头。用闭区间还是左闭右开区别就在怎么避开这个坑。对比项闭区间 [l, r]左闭右开 [l, r)循环条件while (l r)while (l 1 r)mid 计算公式mid (l r 1) / 2mid l (r - l) / 2check 为 true 时l midl midcheck 为 false 时r mid - 1r mid循环结束时l r即为答案l 1 rl 为答案踩坑指数高1 和 -1 都要熟记低边界天然分离闭区间模板不是不能写很多老选手用得很顺但代价是必须背熟两条规则找最大值时 mid 要取上中位数即 (l r 1) / 2false 分支要写成 r mid - 1。任何一条记错轻则死循环重则答案偏一。左闭右开模板把它们简化成r 从第一时刻起就表示“不可能的值”l 表示“可能的值”循环里 l 和 r 永远不相等结束时答案就是 l。我推荐所有刚接触二分答案的人先用左闭右开等理解透了再看心情换。2.2 check 函数的三条设计原则check 是二分答案题的核心模板只是外壳。这里有三条我从大量提交里总结出来的设计原则。第一check 的参数就是候选答案它要回答的问题只能是“能不能满足要求”不要在里面夹带额外计算。第二累加计数时优先用 long long并且能提前返回就提前返回一旦计数已经超过目标值立刻 return true既省时间又防止后续累加溢出。第三处理除零和不可能情况比如候选答案可能为 0 时check 里要先做判断否则除零崩溃或者结果全错。我见过不少人把 check 写得特别“聪明”把贪心、排序、剪枝全塞进去。这没有错但请记住二分答案的复杂度是 O(log V) 次调用 checkcheck 内部越简单整体越稳。能用一层循环解决的不要用两层能在循环里提前退出的不要等到算完。另外check 的命名也有讲究命名成 feasible、ok、check 都可以关键是它的返回值语义要单一不要在函数里顺手改全局变量。改全局变量这条特别容易埋雷因为二分多次调用 check全局状态一旦被带偏第二次调用起结果就全是错的。2.3 题目要求输出小数时直接切到浮点二分有些版本的切绳子问题会要求输出两位小数这时候整数二分就不够用了需要浮点二分。浮点二分和整数模板表面相似实际有三个不同点循环条件不再是 l 1 r而是直接固定迭代次数mid 一律取 (l r) / 2不用考虑取整方向答案输出要按题目要求的精度格式化。固定迭代次数这个细节特别重要——我推荐循环 100 次因为在数据范围 1e9 以内60 次迭代就足以把区间缩到 1e-9 以下100 次是为精度和浮点误差留的冗余而且它比 while (r - l eps) 更不容易陷入死循环。这里顺带解释一个很多初学者困惑的点为什么浮点二分不需要考虑“最后一个 true”的位置。因为浮点区间连续密集60 次折半之后区间长度已经远小于题目要求的输出精度l 和 r 在数值上无限逼近分界点此时你取 l、取 r、取 (l r) / 2在输出精度以内几乎没有区别。所以浮点二分比整数二分简单麻烦的反而是输出格式后面 4.4 小节我会专门讲 eps 的坑。3. 完整实现从数据范围确认到通过评测3.1 写循环前先把数据范围算清楚以切绳子题为例常见约束是 n 不超过 5×10^4单根绳子长度不超过 10^9m 可能大到 10^9。先算几个数答案的最大值不会超过最长的单根绳子也就是 10^9所以二分右边界 r 大概在 10^9 这个量级check 里累加的段数在最极端情况下每根绳子都切成长度 1总段数可能达到 5×10^4 × 10^9 5×10^13这个数远超 32 位整数的表示范围所以计数变量必须用 long long。二分查找的 mid 计算虽然在这个题里 l r 一般不会溢出 32 位但养成用 l (r - l) / 2 的习惯能避免以后在更大数据范围的题目里栽跟头。数据范围这件事值得多说一句。很多人在小样例上跑得欢一提交就全 WA问题往往不在算法思路而在类型精度。写题之前花一分钟把所有极端情况代入算一遍n 取最大、每个数取最大、答案取最大或最小分别会得到什么量级的中间结果。这个习惯能让你少提交很多次也能让你在别人还在调试的时候直接一遍过。3.2 参考代码与逐段说明#include bits/stdc.h using namespace std; long long n, m; long long a[50005]; // 判断每段长度为 len 时能否切出至少 m 段 bool check(long long len) { if (len 0) return true; // 长度为 0 一定可行 long long cnt 0; for (int i 0; i n; i) { cnt a[i] / len; // 这根绳子能切出几段 if (cnt m) return true; // 够了就直接返回省时间防溢出 } return false; } int main() { scanf(%lld%lld, n, m); long long l 0, r 0; for (int i 0; i n; i) { scanf(%lld, a[i]); if (a[i] r) r a[i]; } r; // 左闭右开r 保持为一定不可行 while (l 1 r) { long long mid l (r - l) / 2; if (check(mid)) l mid; // 可行尝试更长的 else r mid; // 不可行缩短猜测 } printf(%lld\n, l); return 0; }几个细节值得单独说明。r 的初值是所有绳子最大值加一加一不是拍脑袋左闭右开模板要求右边界永远指向不可行区域如果 r 直接取最大值当答案恰好等于最长的绳子时这个可行值会被错误地排除在搜索区间外。l 从 0 开始是因为长度 0 无论如何都可行它天然满足“左边是可行区”的约定。mid 用 l (r - l) / 2 而不是 (l r) / 2是为了避免两个大整数相加溢出同时保证 mid 落在可行区但不会等于 r。循环条件写成 l 1 r 而不是 l r是因为我们关心的是“最后一个可行值”让 l 和 r 保持一步之差结束时 l 就是答案不会出现闭区间模板里 l 越界的情况。3.3 用手算验证一遍再提交光写完代码还不够建议按照题意手算一组数据走一遍流程。假设 n 3绳子长度分别是 6、9、12m 5。初始 l 0r 13。第一次 mid 6check(6) 算出 6/6 9/6 12/6 1 1 2 4小于 5不可行r 变 6。第二次 mid 3check(3) 2 3 4 9可行l 变 3。第三次 mid 4check(4) 1 2 3 6可行l 变 4。第四次 mid 5check(5) 1 1 2 4不可行r 变 5。此时 l 1 r循环结束输出 4。和手算一致。整个过程只调用了四次 check每次 check 内部遍历一遍数组所以总复杂度是 O(n log V)V 是答案值域。n 是 5×10^4log V 大约 30整体在几十万次操作量级跑得飞快。这也是为什么二分答案能轻松处理那些直接枚举会超时的题目。如果你提交后遇到运行时间过长先别急着优化 check 内部数一下循环次数对不对——很多“TLE”其实是死循环导致的“永远跑不完”不是真的慢。4. 四个隐蔽 Bug死循环、溢出、边界、精度4.1 死循环的根因是 mid 取整方向我第一次写这题时用的就是闭区间模板代码逻辑和上面差不多但 mid 写成了 (l r) / 2。结果在 l 3、r 4、check(3) 为 true 时mid 算出 3l 被赋成 3下一次循环还是 mid 3区间纹丝不动直接卡死。根源在于找最大值时true 分支要保留 mid也就是 l mid此时 mid 必须取上中位数否则左右边界距离为 1 时 l 永远无法前进。左闭右开模板为什么天然免疫这个问题因为它的 mid 永远取不靠右的值且循环结束条件是 l 1 r两者结合l 到 r 的距离从任何值开始都会严格递减到 1。如果你怀疑死循环最有效的排查方式不是在代码里瞪眼看而是在 check 函数入口加一行日志打印每次循环的 l、r、mid观察距离变化。通常一两轮就能看出问题要么 mid 没变要么 l 或 r 没有更新。记住死循环不是玄学它一定意味着存在某个状态让 l 和 r 不再缩小找到那个状态修复就是一秒钟的事。4.2 check 里的累加溢出第二个坑出在数据规模上。如果你把计数变量 cnt 定义成 int在绳子长度小、n 大的测试点里切出的总段数轻松超过 21 亿此时 cnt 变成负数check 的结果全部错乱提交上去就是答案错误而不是超时非常迷惑。这种 bug 的特点是小样例正常大样例全挂且报错形式不统一。排查方法很简单把答案的极端情况代进 check 手算一遍所有绳子长度为 1、n 取到上限总段数是多少只要超过 int 上限就必须换 long long。同理如果 check 里要累加的是长度总和而非段数也要拿上限值验证一遍。还有一类溢出容易被忽略mid 本身。在有些二分答案题里候选值可能是两个数的乘积或者平方比如求“边长为 x 的正方形面积不超过 S 的最大 x”check 里要做 x 的平方此时即使 x 只有 1e9平方后也是 1e18int 和 long long 都扛不住。遇到这种题要么在 check 里用更大的类型要么换一种比较方式避免乘法。总之凡是涉及乘法和累加的先在草稿纸上算一次上限不要等到提交了再猜。4.3 l 和 r 的初值没给对全盘皆输初值错误的症状往往是答案差 1 或者在特殊测试点出错。常见错误有两种。第一种是 r 直接取某个可行值导致左闭右开区间把正确答案排除在外。比如这题 r 取最长绳子长度当答案是 12 时搜索区间 [0, 12) 根本不含 12答案必然错误。第二种是 l 初值取 1题目要求切不出 m 段时输出 0而 check(0) 你又没特判那么输出就会从 1 开始永远到不了 0。我的做法是l 永远取一个显然可行且符合输出语义的值r 永远取一个显然不可行且比所有候选值都大的值两个边界都写注释标明“为什么这个值一定可行/不可行”。这里强调一个通用准则二分初始区间必须保证答案是区间内的点而不是区间边界的猜测值。很多人在小数据上测不出问题是因为小数据下答案恰好落在区间内部一旦数据变大答案顶到边界就原形毕露。所以在初始化时多问自己一句如果答案等于最大值我的 r 能覆盖到它吗如果答案是 0我的 l 能输出到它吗两个问题都答“能”再往下写。4.4 浮点二分的 eps 陷阱如果题目要求输出小数很多教材会教你 while (r - l eps)然后 eps 取 1e-7。这个写法在值域小的时候没问题但值域一大就翻车如果答案本身在 1e9 量级浮点数的绝对精度只能到小数点后 7 位左右r - l 会永远无法稳定收敛到 1e-7甚至因为舍入误差在某次迭代后不再减小循环退化。更稳的做法是固定迭代 80 到 100 次完全不依赖 eps。实现上还有另一个细节浮点 check 里计算段数要向下取整也就是用 floor(a[i] / len)而不是直接累加浮点数再比较否则会引入精度误差。输出格式是浮点二分另一个容易扣分的地方。要求保留两位小数就直接用 printf(%.2f\n, l)它自带四舍五入。不要自己写什么 ans * 100 再取整的骚操作那只会引入新的误差。除了精度浮点二分还有一个隐含前提check 里的所有中间量都最好用 double别混着用 floatfloat 的精度在答案上限较大时完全不够用。记住浮点二分比整数二分简单但前提是你别把 eps 玩出花来老老实实固定迭代次数稳稳当当输出。下面是这个题以及同类题中最高频的四个问题的速查表建议收藏。症状根因修复程序卡死、不输出mid 取整方向导致 l 不前进改用左闭右开模板或取上中位数小数据对、大数据全错check 里计数变量溢出计数和区间变量统一用 long long答案总差 1r 初始值覆盖不到可行答案r 取不可行上界如 maxLen 1浮点输出不对eps 不合理或取整方式错误固定迭代 100 次用 floor 取整5. 同类题怎么认二分答案的识别套路与两个必会变形5.1 三个特征快速识别二分答案题学完 T1555 这道题价值在于你能认出所有同类题。根据我的经验具备下面三个特征的题大概率就是二分答案。第一题目问的是“最大值最小”或“最小值最大”比如求最短里最长的、最少里最多的第二数据范围在 10^5 以上直接排序或枚举必然超时第三你能在十分钟内写出一个 check(x) 判定某个候选值是否可行而且这个判定的可行性随 x 单调变化。三条都满足基本就可以放心把二分答案作为首选思路。这三个特征其实对应了二分答案的通用解题流程先确定二分对象和取值范围再设计 check最后套模板。流程和 T1555 完全一致只是 check 里的业务逻辑从“切绳子计数”变成了其他判断。做题多了你会发现二分答案从不单独出现它后面永远跟着一个贪心或者一个简单的模拟二分负责降复杂度贪心负责算可行性两者配合才能 AC。5.2 变形一数列分段最小化最大段和一个非常经典的同型题是把一个长度为 n 的数列切成 m 段要求每段数字之和都尽量小求这个“最大段和”的最小值。这题的 check 思路是固定一个候选和 s从左到右贪心分段只要当前段累计和超过 s 就新开一段统计最少能分成多少段段数不超过 m 就可行。注意这个 check 内部用的是贪心但贪心本身不是二分它只是二分内部的判定器。写这类题时我最大的感受是贪心判定的正确性反而比二分模板更容易出错建议先在纸上推几个小数据确认贪心确实能得到最少段数。一个常见的翻车点是 check 里贪心的边界处理。比如累计和刚好等于 s 时要不要立即开新段段数统计是“超过 s 再开”还是“达到 s 就开”这些细节差之毫厘谬以千里。我的建议是写 check 之前用一个不超过 10 个元素的小数组把所有边界情况手工跑一遍确认段数统计的语义和题面一致再提交。5.3 变形二放牛问题最大化最近距离另一个高频变形是在一条数轴上给你若干个点的位置选 c 个点放牛要求牛之间的距离尽可能大求这个最大最近距离。check 的写法是固定最近距离 d从第一个点开始贪心地往后选点只要当前点与前一个选中点的距离大于等于 d 就选它看最终能否选出 c 个。这里的单调性同样一目了然d 越小越容易d 越大越难二分找最后一个可行的 d。这类题的坑在于距离可能是整数也可能是实数如果是实数就切到浮点二分模板注意坐标范围。把切绳子、数列分段、放牛这三个题放在一起对比你会发现 check 的骨架惊人地相似都是“固定一个候选值然后合理地分配或选择最后统计数量是否达标”。区别只在“合理分配”这四个字的业务逻辑。所以二分的代码量其实很少真正的工作量全在 check 的贪心策略上。建议你把这几个模板题都亲手敲一遍体会 check 里贪心写法的共性和差异以后遇到任何“最小值最大”“最大值最小”的字眼条件反射就是二分答案先写 check 再套模板。最后说点个人经验。从这道题开始我写所有二分查找都统一用左闭右开模板l 表示可行、r 表示不可行、答案就是循环结束时的 l。这个统一的代价是每次写题前多花三十秒确认两件事这个值可行吗那个值不可行吗但换来的是我再也没有因为 mid 取整方向翻过车代码的边界也清晰到可以当模板复用。如果你现在还在背模板阶段我的建议是别急着背第二种写法先把一种模板写到条件反射遇到死循环时不是换模板而是回头检查 check 到底是不是真的单调。二分查找五只是一个节点二分答案这套思路会跟着你走过很多更复杂的题值得你多花一个下午把它彻底搞明白。