二分答案这几年在蓝桥杯里的出场率高得有点离谱。省赛出国赛还出而且题型极其稳定不是让你去二分一个数组里的某个数而是让你在“答案的范围”里二分出一个最优解。很多刚入门的朋友总觉得这是个高级技巧其实它底层逻辑特别朴素就是“猜答案然后验证”。一旦你掌握了这套思考方式那一类“最大值最小、最小值最大”的题在你眼里就是送分题。这篇东西我就把二分答案从原理到模板再到真题实战一次性给你掰扯清楚。先说清楚二分答案适合谁看。如果你正在备蓝桥杯不管是C/C组还是Java组、Python组只要大纲里有算法这一块二分答案都是必须拿下的基础算法。它不冷门不偏门做题频率高代码量又小性价比极高。哪怕你只学了排序和枚举也完全能看懂这篇文章。1. 二分答案到底在解决什么问题1.1 从一个最经典的切巧克力问题说起假设你有一块超大巧克力长 H 宽 W现在要把它切成 K 块正方形小巧克力要求每块大小一样、边长是整数问切出来的小巧克力边长最大能是多少。最直觉的做法是什么枚举。从边长 1 开始往上试每试一个边长就把整块巧克力按这个边长去切一遍统计能不能切够 K 块能就继续加大边长直到切不够为止。这个做法没问题但复杂度很吓人。巧克力边长每维最多 10^5你要枚举 10^5 次每次还得筛选所有大巧克力最坏情况下乘起来就爆炸了。但你想一下边长这个变量有个特别重要的性质如果边长为 x 时能切出 K 块那么边长为 x-1、x-2 乃至 1 的时候一定也能切出至少 K 块。反过来如果 x 时切不够那 x1、x2 就更不可能够。这种“答案越大越难满足”的特性在数学上叫单调性。有单调性就意味着答案不是散乱分布的。所有“能满足条件”的边长会连成一片“不能满足”的边长也会连成一片中间只有一个分界线。我们要找的就是这条分界线上最右边的那个可行点。顺着这个思路我们根本不需要从 1 到 10^5 挨个试直接二分取中点 mid判断一下边长 mid 能不能切够 K 块能说明答案在右边不能说明答案在左边。每一轮排查一半的区间最多 log2(10^5) 次约 17 次就结束了。这就是二分答案的全部精髓不直接求解最优化问题而是去猜一个答案然后快速验证它合不合法。1.2 二分答案和二分查找是两回事很多人一听到“二分”就想到有序数组里找数字然后开始纠结数组下标、mid 减一加一的细节。二分查找是在“已排序的数据”里找一个确定的值它的搜索空间是数组下标。而二分答案的搜索空间是“解的范围”数据范围可能大得吓人可能从 0 到 10^9但没关系因为每次判定我们只关心 check(mid) 返回真还是假。类比一下二分查找像是在一条已排好队的队列里找某个特定的人二分答案像是在猜一个神秘数字你每猜一次对方只会告诉你“大了”还是“小了”然后你不断缩小猜测范围。这两个东西在代码形态上几乎一样但思维方式完全不同。二分答案的核心从来不是二分本身而是“如何快速验证一个答案是否可行”——也就是 check 函数的设计。很多同学二分模板背得滚瓜烂熟遇到题目照样写不出来问题就出在 check 上。2. 从原理到模板三个必要条件缺一不可2.1 单调性怎么判断能用二分答案的题解空间必须有单调性而且你要能明确说出是哪种单调答案越大越容易满足条件。典型如“求最短跳跃距离的最大值”——你让最小距离定为 5可能很容易定为 100石头间距不够就得疯狂移石头可行性下降。答案越大越难满足条件。典型如分巧克力——切 1 边长很容易切够切 100 边长就切不够了。不管哪种方向你只需要能回答一个问题给你一个候选值 x你能不能判断出它可不可行可以那就二分不可以那你先别用二分答案把判定问题想明白再说。判断单调性有个偷懒的实操方法拿一个非常简单的小数据手写结果看答案变大时可行区间是哪种走向。比如“牛舍间距”问题你让间距等于 1几乎所有位置都能放牛让间距等于最大值可能一头牛都放不下。这就清晰了是递减型单调。2.2 check 函数是灵魂我见过太多人花大量时间研究二分边界却不肯在 check 函数上做文章。其实边界问题总共就那么几个套路背下来就够了check 函数才是拉开差距的地方。check 函数大概可以分成两类第一类贪心 计数。最常见。比如分巧克力check(x) 要做的事情是遍历所有大巧克力计算每一块能分成多少个 x×x 的小块然后累加看总数是否大于等于 K。每块的贡献是 (H / x) * (W / x)注意这里两个除法都是整数除法对应实际能切出多少排、多少列。不能先乘再除不然误差会把你带沟里。第二类模拟 计数。比如“跳石头”这种题你想让最小跳跃距离至少是 x那就从起点开始挨个检查每块石头。如果当前石头和上一块保留下来的石头距离小于 x就把这块石头移走否则保留它继续往后走。最后统计移走的总数看是否不超过允许移除的 M 块。这两类 check 都有个共同点复杂度通常接近 O(n)而 n 在蓝桥杯里一般是 10^5 级别。外层二分大约要跑 20 到 31 次乘起来就是 2×10^6 到 3×10^6 级别在一秒内轻松跑完。这就是二分答案的威力它把那种看起来很吓人的最优化问题降到了 log 倍线性复杂度。2.3 边界、数值类型和防止死循环如果你写过二分一定被死循环折磨过。这里我不给抽象理论直接给结论你把这两个模板焊死在脑子里。模板一求满足条件的最大值答案在可行区间的最右端。这里我们要找的是“最后一个可行的位置”所以 mid 要偏向右端点。bool check(int x); int solve() { int l 1, r 1e9; // 根据题目调整上下界 while (l r) { int mid (l r 1) 1; if (check(mid)) { l mid; // mid 可行答案可能更大 } else { r mid - 1; // mid 不可行往左找 } } return l; }模板二求满足条件的最小值答案在可行区间的最左端。bool check(int x); int solve() { int l 1, r 1e9; while (l r) { int mid (l r) 1; if (check(mid)) { r mid; // mid 可行答案可能更小 } else { l mid 1; // mid 不可行往右找 } } return l; }记住一个 key point当区间长度剩 2 的时候如果 mid 往左偏不加 1而你的更新又是 l mid那 l 就永远不会动死循环。所以“求最大可行”必须配 mid 上取整即 (l r 1) / 2而“求最小可行”用不带上取整的写法因为更新时是 l mid 1会强制把区间缩小。数值范围方面蓝桥杯经常出现 10^9 甚至更大的上界这时候注意两件事一是 mid 计算时 l r 可能超 int保守起见用 long long二是在 check 内部所有乘法也可能爆 int。比如巧克力边长 10^5切出来的块数如果直接用 int 存单块可以贡献上万多块累加后完全可能超 2^31。建议凡是可能产生较大数值的量一律 long long别心存侥幸。3. 实数二分与特殊细节的处理3.1 什么时候要用实数二分蓝桥杯里有一部分题要求答案保留小数点后几位或者干脆答案是浮点数。最典型的比如“切绳子”给你若干根绳子要切成若干段等长的小段问你每段最长多少。边长不一定整数这里的答案就是实数。实数二分和整数二分的思路完全一样但写法上有差异因为它不再有“整数边界”可以收敛到具体值。通常不判断 l 和 r 是否相等而是靠迭代次数或者精度阈值来控制。double l 0, r 1e9; for (int i 0; i 100; i) { // 固定迭代 100 次稳妥 double mid (l r) / 2; if (check(mid)) { l mid; // 不够大往右 } else { r mid; // 太大了往左 } }为什么固定迭代 100 次而不是 while (r - l eps)因为 eps 设多少是个玄学。如果你设 1e-6但实际答案范围很大有可能迭代到几百次才能满足而且 check 函数里浮点数运算有精度损失过于依赖 eps 判断容易在极端数据下出错。固定迭代 100 次对于 10^9 范围的初始区间每次减半100 次后区间长度约为 10^9 / 2^100这个精度早就超出 double 的表示能力了直接输出 l 或 r 的某个格式化结果即可。3.2 实数题的一个大坑输出格式实数题经常要求你保留几位小数有的比赛允许任意精度但蓝桥杯一般要求保留固定位数。很多人在这一步栽跟头二分结果算出来了输出时四舍五入库没写对或者直接 cout 默认输出 6 位小数结果被扣分。C 里建议这样处理#include cstdio printf(%.2f\n, ans); // 保留两位小数或者用 cout 的话cout fixed setprecision(2) ans endl;注意一个问题输出两位小数但答案本身可能是 5.9999999 这种二分误差导致的近似值。如果你想输出 6.00但 printf 按 5.99 给你舍入那就是精度问题。所以有些选手会输出 ans 1e-9即在提交前给结果加一个极小的偏移量修正浮点误差。这个方法在竞赛圈很常见但用的时候要特别小心不能加多了否则会把本来 5.999999 这种正确结果硬改成 6.000001照样不对。一般加 1e-7 到 1e-9 这个量级具体看题目精度。3.3 二分初始上下界的设定技巧上下界设得不好轻则多跑几轮重则直接 WA。我的习惯是下界如果问题是求边长、长度、距离这类答案下界通常从 1 或 0 开始。但注意部分问题的合法答案可以是 0比如没有任何可行方案时输出 0这时候下界必须从 0 开始。上界如果没有明确给定一个省事的安全值是题目中可能出现的最大值比如所有元素和、最大边长等。比如切绳子所有绳子长度之和除以段数是一个很紧凑的上界你也可以直接用 1e9 这种大值二分几十次照样能得到正确答案只是可能浪费几次迭代无伤大雅。不过这里有个容易忽略的细节如果上界设得不够大正确答案恰好在上界附近你二分出来的答案会比真实值小一截。比如所有绳子都是 10段数要求 1正确答案是 10而你把上界设成了 8那永远找不到 10。所以上界尽可能取题目描述里没有“一刀切上限”时的保守最大值宁大勿小。4. 真题级别的完整拆解代码一行行说清楚4.1 分巧克力入门必练的计数型 check题目原型有 N 块长方形巧克力每块尺寸是 H_i × W_i现在要切出至少 K 块边长相同的正方形巧克力问最大边长。切的时候只能按整数边长切不能拼接。check 函数这样写bool check(int x, int N, int K, vectorint H, vectorint W) { long long cnt 0; for (int i 0; i N; i) { cnt (long long)(H[i] / x) * (W[i] / x); if (cnt K) return true; // 提前退出省一点时间 } return false; }为什么每块是 (H / x) * (W / x)你可以想象把长边按照 x 切成若干段宽边按照 x 切成若干段交叉网格就是若干个小方格。这是整数除法如果恰好不能整除多余的部分直接浪费。比如 H5, x25/22说明长边只能放两排剩 1 单位废弃。主函数这么写int main() { int N, K; cin N K; vectorint H(N), W(N); int maxSide 0; for (int i 0; i N; i) { cin H[i] W[i]; maxSide max(maxSide, min(H[i], W[i])); } int l 1, r maxSide; while (l r) { int mid (l r 1) 1; if (check(mid, N, K, H, W)) l mid; else r mid - 1; } cout l endl; return 0; }这里上界取所有巧克力边长中的最小值是一个很实用的优化。因为你想切 x×x 的正方形如果 x 比某一维还要大那这一维根本没法切。用所有巧克力里最短边作为全局上界保证至少有一块巧克力有可能切出这个边长逻辑上完全闭合。这题有几个常见 WA 点一是 check 里乘法溢出二是 maxSide 初始为 0 导致 l r三是把上界设成所有巧克力的最大边长而不是最小边长结果做了很多无用二分不至于 WA但没必要。4.2 跳石头模拟型 check 的标杆题目原型起点到终点距离为 L途中有 N 块石头每个石头离起点距离给定。你最多可以移走 M 块石头不能移起点和终点问移完之后从起点到终点依次跳跃相邻落点之间距离的最小值的最大值是多少。这个题看起来绕但 check 的意图很清晰如果要求最短跳跃距离至少是 x你需要移走几块石头bool check(int x, int L, int N, int M, vectorint stones) { int last 0; // 上一个保留的落点 int removed 0; for (int i 0; i N; i) { int cur stones[i]; if (cur - last x) { removed; // 这块石头太近了移除 } else { last cur; // 保留它下次从它开始比 } } if (L - last x) removed; // 最后一段也要检查 return removed M; }注意循环里那个 if-else 的语义如果两个相邻保留石头的距离小于 x这块石头必须移除。这里有个关键点移走的是“当前这块”而不是“上一块”。你从前往后扫上一块是刚保留的它前面的贪心决策已经做完了不能回头改否则贪心性质就破坏了。还要注意最后一个特判终点和最后一块被保留石头之间的距离也可能小于 x此时终点不能移除只能把最后一块石头移除所以 removed 要加一。很多初学者漏掉这个判断样例能过一提交就 WA。主函数里二分时下界可以从 1 开始上界用 L。然后套模板一因为我们要的是“满足 removed M 的最大 x”。这类模拟型 check 的复杂度是 O(N)加上外层二分大约三十次总复杂度 O(N log L)L 如果到 10^9也就是约 30 次扫全量数组3×10^6 级别操作比赛环境完全跑得动。4.3 进击的奶牛最大化最小间距的换皮题题目原型有 N 个牛棚位置M 头牛要放到这些棚里要求相邻两头牛之间的距离尽量大问这个最大最小距离是多少。其实这题和跳石头本质上是一种模型只是 check 的方向反过来了。这里 check 是给定距离 x你最多能放下几头牛bool check(int x, int N, int M, vectorint pos) { int cnt 1; // 第一头牛放在第一个牛棚 int last pos[0]; for (int i 1; i N; i) { if (pos[i] - last x) { cnt; last pos[i]; if (cnt M) return true; } } return false; }这道题告诉我们一个很重要的经验二分答案的主题千变万化但 check 的核心思想就两种一种是“给定约束算出最多能放几个/切几块”另一种是“给定目标算出最少要移走几个/操作几次”。你能把题目归约到这两种范式之一基本就离 AC 不远了。这题的另一个价值是不用动脑子的位置牛棚位置要先排序因为 check 里需要按从左到右扫。如果忘了 sort所有贪心判断全乱套这属于低级但常见的错误写代码前先想清楚数据要预处理成什么顺序。5. 那些年我们踩过的坑一次性总结给你5.1 死循环到底怎么破二分答案死循环的原因九成以上集中在模板一和模板二混用。你自己写的时候如果发现程序卡死了先看不变量区间是否每次都在缩小。模板一用了 mid (l r) 1但更新 l mid且 l 恰好等于 mid区间没变小死循环。模板二用了 mid (l r 1) 1但更新 r midr 恰好等于 mid区间也没变小死循环。所以我的习惯是每次写完二分先手动跑一遍区间 [1, 2] 的极端情况看看 mid 能不能把区间缩成 [1,1] 或 [2,2]。这个动作花不到十秒但能杜绝一整类 bug。如果你用的是 C 模板 lambda 来写 check一定要确保 check 的捕获方式正确别在内部把可变量传引用搞出意外修改。我遇到过一次check 里顺手改了一个全局计数变量导致第一次调用结果正确第二次调用状态全乱排查了很久才发现。建议 check 函数尽量做成纯函数输入一个 x输出 bool不修改任何外部状态。5.2 初始化边界导致结果恒为 0很多时候你二分出来的答案是 0不是因为你写的算法错误而是下界设错了。比如某些题允许答案为 0你却不小心把下界设成 1导致根本检查不到 0 的情况。反过来的情况也存在下界设成 0但题目要求答案至少是 1那你可能输出 0WA。我处理这类问题的方式是先想清楚“这道题的答案合法最小值到底是什么”再决定下界。拿不准的时候把下界设成一个肯定小于等于答案的值比如 0但要保证 check(0) 一定返回 true。如果 check(0) 返回 false那麻烦就大了。所以有些题你会看到有人这样写int l 0, r MAX; while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }此时 check(0) 必须为 true这样区间左边才是可行的。如果你发现 check(0) 恒 false那说明这个题根本没有可行解或者你的 check 写反了。5.3 时间复杂度与常数优化二分答案的总复杂度 O(log(上界-下界)) × O(check 复杂度)。以蓝桥杯常见的 1 秒时限来说如果 check 是 O(N)N 10^530 次循环就是 3×10^6很安全。如果 check 是 O(N log N)比如内部要排序或者用 set那总复杂度是 30×10^5×log勉强能过但如果题目数据到 2×10^5 就要小心常数了。如果 check 是 O(N^2)那想都别想一定超时必须换思路。这里有个实战优化技巧在 check 的循环里一旦计数达到目标值立刻 return true不需要扫完全部。比如分巧克力cnt K 就直接返回放奶牛cnt M 就直接返回。虽然最坏情况下该扫完还得扫完但很多数据根本到不了最坏情况这个提前退出能帮你省下可观的运行时间。反之那种必须统计总数才知道是否满足的题比如“移走的石头不能超过 M”你必须扫到尾才知道结论那就没办法提前退出了。写 check 之前先想清楚它属于哪一类就知道能不能提前剪枝。5.4 浮点数二分的输出陷阱补充前面说到了加偏移量但我要强调不是所有题目都需要加。你可以用一个统一的稳妥策略把所有浮点运算全部用 double输出前先四舍五入到目标精度。比如保留两位小数就 (ans 0.005) 后再格式化当然 printf 的 %.2f 本身会四舍五入所以更推荐的方式是double ans l; // 二分结束取 l 或 r 都可以 printf(%.2f\n, ans); // 基于舍入但受误差影响 // 保守一点 printf(%.2f\n, ans 1e-8);加 1e-8 的作用是把 6.999999999 这种因为二分迭代不够导致的底部近似值推到 7.0。但如果你把 1e-6 加进去可能把真正该是 6.999 的数错误地进位成 7.000。建议偏移量不要超过题目输出精度的 1/100。6. 从蓝桥杯到更远的竞赛场这套思路值多少钱二分答案不是蓝桥杯专属它几乎渗透到所有算法竞赛里。ACM、程序的考试、面试算法题甚至日常业务里某些资源分配问题都可能用到同一个思想。你一旦把 check 函数的设计思路练熟了以后遇到很多优化问题都会多一把趁手的工具。我自己备赛蓝桥杯的时候有一段很深刻的教训。第一次做分巧克力题我直接枚举以为 N 不大没关系结果样例过了、大数据超时。后来被学长指点才第一次接触“二分答案”这个词。当时我最大的卡点不是二分边界而是不习惯“把一个最优化问题硬生生变成判定问题”这种思维。它就像是把你递进求解的过程改成了对答案空间做二分猜测然后用判定去逼近。我花了整整一周反复练各种 check 写法从那以后凡是有单调性的优化题我第一反应就是二分答案。如果你现在也被这类题卡住我的建议是不要急着刷难题先把三件事做扎实一是把两个整数二分模板在纸上推导三遍搞清楚为什么一个加一、一个不加一二是把上面三道经典题亲手 AC 一遍不要只看思路代码必须自己敲三是自己去总结 check 函数的范式看到一个新题先判断是“计数型”还是“模拟型”再动手写。二分答案这道坎跨过去之后你会发现它带给你的不仅是会做一类题更是一种思维方式上的升级当你面对一个看似无从下手的最优化问题时先别慌问问自己如果给我一个最终答案我能不能快速验证它如果能那这道题大概率就是二分答案。这个思路能帮你省下大量在考场上盲目尝试的时间。
