说实话第一次见到二分答案这个说法的人很容易被绕进去——明明二分查找我熟啊有序数组里找个数左右指针一夹O(log n)搞定。但二分答案完全不是一回事。它不是在数组里找某个值而是在一个答案区间里猜最优解然后写一个判定函数去验证这个解合不合法。这个概念在蓝桥杯里出现频率极高尤其是省赛和国赛的填空题、编程大题里几乎每年都有它的影子。很多同学拿到题第一反应是贪心、DP、模拟一算复杂度直接超时但如果换成分二分答案的思路代码量短思维量小跑得还飞快。这篇帖子我就把二分答案从思想、适用场景、代码模板到真题级别的例题拆解和高频坑位一次讲透。1. 二分答案的核心思想从猜答案到验答案1.1 二分查找和二分答案到底差在哪先理清一个基础概念。普通二分查找操作对象是已经排好序的数组目标是找到某个元素的下标。它的前提是数据本身有序本质是在做检索。二分答案的操作对象不是数组而是一个具有单调性的答案空间。你事先不知道答案是多少但你能确定答案落在一个范围 [L, R] 内。于是你在这个范围里猜一个值 mid然后写一个函数 check(mid)判断如果答案是 mid能不能满足题目的约束条件。根据 check 的结果把搜索区间砍半继续猜直到逼近最优解。核心区别一句话二分查找是在已知有序数据里找目标二分答案是在未知答案区间里猜最优值用判定来代替搜索。这个转化非常关键因为它把一个求最值的问题硬生生变成了猜一个值然后验证它是否可行的问题。打个比方。想象你在猜一个数字规则是对方每次只告诉你大了还是小了。这个时候你每次报一个数根据反馈缩小范围最终锁定目标。二分答案就是这个套路——只不过大了小了的反馈来自你自己写的 check 函数。1.2 单调性是二分答案的命根子为什么二分答案能成立因为答案的可行性必须随答案值单调变化。什么意思就是说如果答案是 X 可行那么比 X 更宽松的答案一定也可行如果答案是 X 不可行那比 X 更严格的答案一定也不可行。这个性质一旦成立整个值域就被划成了一段可行、一段不可行两段你才能在中间来回切。举一个最经典的例子。假设你有 n 根木棒每根长度不一现在想把它们切成 m 段长度相等的小段问每段最长能有多长。注意这个单调性每段长度如果取得很短那一定能切出足够多的段数每段长度取得越长能切出的段数就越少。于是能否切出至少 m 段这个可行性随答案增大是单调递减的。你就能二分这个长度。要是没有单调性比如你这么切就可行换个不那么严格的答案反而不可行那就不能二分。这就像猜数字游戏里对手一会儿说大了一会儿说小了根本不按套路出牌你没法玩。1.3 判定函数 check整个算法的灵魂二分答案的所有难点基本上都压在 check 函数上。check(mid) 要做的事情是给定一个候选答案判断它是否满足题目约束。这个函数的实现方式没有固定套路常见的有几种配合贪心比如按顺序扫描一遍统计需要多少步才能满足条件配合模拟直接按照规则跑一遍流程看是否超出限制配合数据结构比如用并查集判断连通性用线段树维护区间特征配合 DP在特定情况下做可行性动态规划。每次二分都要调用一次 check整个二分过程大概调用 O(log R) 次。如果答案范围是 1 到 1e9也就是大概 30 次左右范围再大点也就在 60 次以内。所以 check 的复杂度直接决定总复杂度。比较常见的情况是 check 写成 O(n)整体复杂度 O(n log R)对于 n 在 1e5 级别、时间限制 1 秒的题完全能扛住。记住一个心法写出 check 的那一瞬间你其实已经解决了 80% 的问题。二分框架谁都会写难点在于你怎么把一个求最优解的问题转换成给定答案判断是否可行的问题。2. 题目特征识别看到什么信号就该想到二分答案2.1 两类最典型的问法在蓝桥杯和各类算法竞赛里二分答案的题有非常明显的脸谱。第一类是最大值最小化第二类是最小值最大化。凡是题干里出现类似使得最大值尽可能小或者使得最小值尽可能大的描述基本可以无脑往二分答案的方向想。为什么这两类问法天然适配二分答案因为最大和最小往往出现在约束关系的两端而约束关系通常具备单调性。比如你要安排一个序列分成若干段每一段有一个和问所有段的和的最大值最小是多少。段和的最大值越大就越容易把序列分得足够少可行性单调段和的最大值越小分割就越严格可行性就变差。这个单调性一出现二分答案就顺理成章。2.2 答案必须落在一个明确的区间里能不能二分还要看答案的搜索空间是否明确。大多数情况下答案要么是正整数要么是浮点数给你一个大概的上下界。比如每段木棒长度最长不会超过原始最长那根木棒的长度跳跃距离最小值最大不会超过起点到终点的总距离。上下界明确二分区间就定下来了。如果遇到答案范围巨大比如 0 到 1e18别慌照样能二分只是多循环几次而已。整数二分一次循环砍半1e18 也就 60 次依然很快。浮点数答案更是如此甚至可以直接循环固定次数比如 100 次精度远超需求。2.3 不适合二分答案的情况也有不适合二分答案的场景别硬套。答案的可行性和数值之间没有单调关系。比如某些图论问题改变一个参数后可行性可能是震荡的这种二分就是空中楼阁。判定函数比直接求解还难写。如果 check 本身涉及复杂的动态规划或者搜索那每次二分都要跑一遍重活整体复杂度可能直接爆炸。数据范围小到直接暴力枚举答案就能过。比如答案范围只有 1 到 1000直接枚举每一个值然后 check 一下复杂度也就是 1000 次 O(n)没必要二分。3. 二分答案代码模板与边界细节3.1 整数二分的两种写法一个致命细节决定成败整数二分最坑的地方就是边界更新。这里直接给你两个模板背下来然后理解背后为什么这样写比临场推导稳得多。第一种写法求最小的可行解也就是在可行域的左端点附近找答案。bool check(int x) { // 判断答案 x 是否可行 } int main() { int l 0, r 1e9; // 根据题目调整 while (l r) { int mid (l r) / 2; if (check(mid)) { r mid; // 可行则尝试更小的值 } else { l mid 1; // 不可行则必须往大走 } } cout l endl; }第二种写法求最大的可行解也就是在可行域的右端点附近找答案。bool check(int x) { // 判断答案 x 是否可行 } int main() { int l 0, r 1e9; while (l r) { int mid (l r 1) / 2; // 注意这个 1 if (check(mid)) { l mid; // 可行则尝试更大的值 } else { r mid - 1; // 不可行则往小走 } } cout l endl; }为什么第二种写法里 mid 要取 (l r 1) / 2你假设 l 3r 4如果不加 1mid (34)/2 3。如果 check(3) 可行执行 l mid结果 l 还是 3r 还是 4下一轮依旧是 mid 3死循环。加了 1 之后mid 4要么 l 变成 4要么 r 变成 3区间必然缩小。这是所有整数二分死循环的根源99% 的二分答案死循环都出自这里。3.2 浮点数二分的精度控制浮点数的二分和整数稍微不同因为你不能指望 l 和 r 最终相等只能逼近。两种常见控制方式第一种固定循环次数。比如循环 100 次保证精度。这种方式最稳因为不会因为答案范围过大而精度不足。double l 0, r 1e9; for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) { l mid; } else { r mid; } }第二种精度阈值控制。循环条件写成 while (r - l eps)其中 eps 取 1e-7 或者更小。这种写法容易踩坑如果答案范围很大或者很小r - l 可能永远大于 eps 导致超时或者过度循环。我个人更推荐固定循环 80 到 100 次省心不爆时间。还有一个重点输出格式。蓝桥杯这类比赛经常要求保留几位小数你在输出的时候要小心。保留两位小数输出 3.14 这种直接用固定精度输出。但如果你算出来的答案是 3.141000题目要保留 2 位可能要求四舍五入或者截断务必看清题目要求。3.3 check 函数怎么写才高效check 函数是二分答案里唯一的变量它写得好不好直接决定题目能不能过。几个经验尽量把 check 的时间复杂度压到 O(n) 或者更低。O(n log n) 在里面套一层二分总复杂度 O(n log n log C)n 到 1e5 级别就开始吃紧了。不要在 check 里做重复初始化。比如每次循环都重新 new 一个数组、清空一个容器这非常致命。把需要复用的数据结构放到外层在 check 里只用 O(1) 或 O(n) 的方式更新。能用贪心就用贪心因为贪心实现简单、常数小。大部分二分答案题目的 check 都是配合某种贪心策略。3.4 一个通用的题目区间分析技巧拿到一道题怎么定 l 和 r不要随手写 0 和 1e9。先看题面如果答案是长度、数量下界通常是 0 或 1上界是某个显式给定的最大值比如所有木棒长度之和、两点间总距离、数组最大值如果答案是浮点数下界可能是 0上界要算一下理论极端值如果答案要求是整数还要特别注意你最终输出 l 还是 r取决于你用的是哪个模板。下面的排查方式可以帮你想清楚先在心里把答案猜成中间值然后手算几组数据看 check 的结果是不是和题意一致。如果答案从可选范围的最大值开始一直测到最小值发现可行性是可行...可行...不可行...不可行这样的分段那二分答案完全可以上。4. 典型例题深度拆解三道题彻底吃透套路4.1 例题一分木棒最大化可行解题目场景有 n 根长度不一的木棒长度存在数组 a 里。现在要把它们切成若干段要求所有段长度相等段长为正整数最终至少能得到 k 段。问每段最长能有多长。这道题是二分答案的入门经典很多竞赛教程里都有类似题目。先看单调性段长越大能切出来的段数越少段长越小能切出来的段数越多。能否得到至少 k 段这个判定结果随段长增大而单调变化所以可以二分答案。check 函数怎么写非常朴素遍历每一根木棒假设当前段长是 mid那么第 i 根木棒能贡献的段数就是 a[i] / mid整数除法累加所有贡献如果总数大于等于 k就返回 true否则 false。bool check(int mid) { long long cnt 0; for (int i 0; i n; i) { cnt a[i] / mid; if (cnt k) return true; // 提前退出省时间 } return false; }注意两个细节第一cnt 要开 long long因为 n 最多 1e5每根长度 1e9加起来段数可以轻松超过 int 范围第二提前判断 cnt k 时立刻返回 true这是个很小的常数优化但数据大的时候有效。二分区间怎么定l 1段长至少为 1r 所有木棒长度的最大值段长不可能超过最长的单根木棒。这里用的是求最大可行解的模板所以 mid 要加 1。这道题有个变种是切巧克力本质一模一样只是把木棒换成了巧克力块。核心都是给定一个答案值统计它在中每个物体里能切出多少份。这类题做一道相当于做十道。4.2 例题二跳石头最小值最大化这个场景在算法竞赛里流传很广我见过各种版本的改编。题目大致是有一条宽度为 L 的河从起点到终点有若干块石头位置坐标分别是 p[1] 到 p[n]。现在要移走其中 m 块石头不能移走起点和终点使得任意相邻两块石头包括起点和终点之间的距离的最小值最大化。问这个最大化的最小值是多少。先转换为二分思路假设跳跃距离最小值是 mid问能不能在移走不超过 m 块石头的前提下保证任意相邻两块石头之间的距离都不小于 mid。这里可行性随 mid 增大单调变化mid 越小越容易满足mid 越大要移走的石头就越多超过 m 就不可行了。check 函数用贪心。思路是从起点开始维护上一个没被移走的石头位置 last然后依次向后扫描每一块石头。如果当前石头和 last 之间的距离小于 mid说明这块石头应该被移走移走次数 cnt 加一否则保留这块石头把 last 更新到当前石头位置。扫描结束后判断 cnt 是否不超过 m。bool check(int mid) { int cnt 0; int last 0; // 起点位置为 0 for (int i 0; i n; i) { if (p[i] - last mid) { cnt; } else { last p[i]; } } return cnt m; }这里还有一个容易忽略的点终点也要参与判断。扫描完所有石头后你还需要看最后一块保留的石头到终点 L 的距离是否小于 mid。如果小于 mid理论上最后一段距离不满足条件但这时你已经没有可以移动的中间石头了怎么办正确做法是在石头序列的最后虚拟地加入终点让终点也参与贪心判断。很多初学者在这个细节上丢分因为样例里刚好没有触发这种情况但实际数据里一测就炸。我没有在 check 里显式处理终点但实际代码里要么把终点的坐标作为一个额外的待判断点要么在循环结束之后单独再判断一次最后那段距离两种方式等价。这道题背后就是最小值最大化的典型结构。它和分木棒的区别就在于 check 的贪心策略完全不同一个是统计能切出的份数一个是统计需要移走的个数。4.3 例题三浮点数答案的二分切绳子问题题目场景有 n 条绳子长度都是浮点数需要切出 k 段长度相等的绳子问每段最长能有多长结果保留两位小数。这题也是经典。整数版本往往简单但一旦答案变浮点数很多同学就不知道怎么控制边界和精度。二分思路不变答案区间是 [0, 最长绳子的长度]check 函数同样是统计每条绳子能贡献的段数。check 函数的代码bool check(double mid) { int cnt 0; for (int i 0; i n; i) { cnt (int)(len[i] / mid); if (cnt k) return true; } return false; }注意浮点数二分不能简单用 l mid 或 r mid 去等永远不可能等。我的习惯是固定循环 100 次这样不管答案范围多大精度都足够。如果题目要求保留两位小数我在输出时再固定格式不会因为浮点误差打印出 3.14 而实际期望是 3.14 但二进制表示可能略偏。这里有一个特别常见的坑输出精度。竞赛环境里如果用 C 的printf(%.2f\n, l)理论上没问题但二分 100 次后 l 的精度可能在一个极小范围内浮动某些极端情况下四舍五入的结果会和标准答案差 0.01。稳妥的做法是算完答案后加上一个极小偏移量再输出比如l 1e-9。这是处理浮点数保留位数的老套路了。4.4 三道题背后的共同套路这三道题表面上场景完全不同一个切木棒一个跳石头一个切绳子但骨架完全一样确定答案形式整数/浮点数和搜索区间把最优解翻译成一个判定条件写一个 check(mid)用贪心或模拟判断可行性套二分模板调整上下界更新方式小心边界细节包括 long long、浮点偏移、题目输出格式。如果你能把这个流程刻在脑子里遇到任何看起来像二分答案的题第一步不是急着写代码而是先定义清楚什么是可行解。5. 蓝桥杯实战中的高频坑与排查实录5.1 边界条件出错左边界该取 0 还是 1很多同学在小数据上盯着样例跑通过就觉得没问题结果一提交就 WA。最常见的原因之一是下界设错。比如切绳子问题如果所有绳子都短于 1 米但题目限制你切出的每段长度至少 1那下界就应该设 1再比如分木棒如果你把 l 设成 0check(0) 会出现除零问题。我见过有人把l 0, r 1e9一写到底不去想答案有没有可能为 0。如果题目的答案最小值可以是 0那没问题但如果题目要求正整数你就要把 l 至少设为 1。还有一种情况是上界设小了。比如一个数组里最大值是 1e9你自信地把上界设为 1e9结果答案是 1e9 1 或者 1e18那永远二分不到正确答案。排查技巧先手动构造一个所有可能答案的极端数据跑一遍你的二分区间。比如全部数据都是最大值看你的 r 够不够全部数据都是最小值看看 l 是否会导致 check 出错。这种极端测试两三组边界问题基本都能暴露。5.2 二分死循环mid 取整方向惹的祸死循环问题前面讲过根源基本都在于求最大可行解时 mid 没加 1。但有时候你明明加了 1还是死循环那就要看 mid 的计算是否溢出了。当 l 和 r 都很大比如 l 1e9r 1e9l r可能超出 int 范围。虽然在 C 里 int 最大是 21 亿多两个 10 亿相加到 20 亿还好但如果是 l 1e18那就直接溢出。解决方法很简单写成mid l (r - l) / 2或者mid l (r - l 1) / 2避免加法溢出。这不仅是二分答案的坑是所有二分写法的通用问题。定位死循环的小技巧当你的程序卡住不输出先在脑内模拟一轮 l 3, r 4 的情况看每次 mid 取什么值l 和 r 会不会更新。如果更新之后 l 还是 3、r 还是 4基本就是取整方向错了。还有一种情况是 check 函数本身对 mid 完全相同的输入返回了不同结果那也会造成死循环但这属于 check 的 bug需要单独测 check。5.3 二分超时不是二分慢是 check 太重二分答案很少因为二分本身超时因为 30 到 60 次循环真的很快。超时基本都出在 check 函数里。一个典型的例子check 内部用了排序。比如你在 check 里对数组做一次 O(n log n) 排序总复杂度变成 O(n log n log C)当 n 1e5 时大约要做 30 次排序时间可能飙到接近上限。更好的做法是在二分之前先把数组按某种规则预排序在 check 里只做线性扫描。另一个典型的例子check 内部频繁申请容器。比如每次二分都 new 一个 vector用完就释放30 次循环下来内存分配的常数非常夸张尤其数据量大时直接拖垮性能。把容器放到外头复用在 check 里更新长度或内容即可。最后提一个蓝桥杯常见的优化点输入输出。一些题的数据规模很大如果用了慢速的 cin / cout 并且没有关闭同步可能输入就占了大量时间。通常我在竞赛环境下都会加上ios::sync_with_stdio(false); cin.tie(nullptr);必要时直接用 scanf / printf。二分答案本身不是瓶颈但输入输出可能是。5.4 check 的贪心策略写错样例对了却全盘皆输这是最隐蔽的坑。二分答案的 check 里用贪心时贪心策略如果错了可能小样例侥幸通过大数据一波带走。我自己的教训是写完 check 后不要只跑题目给的样例要自己构造几个针对性数据验证贪心选择是不是局部最优。举例来说跳石头问题里如果遇到一块石头距离 last 小于 mid你是移走它还是保留它而移走别的石头常规做法是移走它因为保留它会限制后续所有石头的最小距离都变大并不划算。这个往后看一步的逻辑是贪心成立的核心。类似的问题还有分木棒时是否需要优先消耗长木棒、短木棒大多数情况下顺序无关因为段长是固定的每根木棒贡献的数目只跟它自身长度有关。如果你在 check 里用了某种排序或者优先队列写完之后花一分钟想三个问题当前选择会不会影响后续的选择如果影响是否有反例反例能不能构造出来想不出反例才敢提交。6. 从这道题延伸出去二分答案的各种变形二分答案远不止切木棒和跳石头。它还能和很多算法组合形成更新颖的题目。二分 前缀和比如分割数组使得每个子段和最大值最小这类题check 里需要扫描前缀和或者维护当前段的和是二分答案与贪心的经典结合。二分 并查集比如给一些边问在不超过某个权值的情况下能否连通某两个点可以把边权排序二分答案check 里用并查集判断连通性。二分 BFS/DFS有些搜索题要求最小化路径上的最大值可以先二分答案然后用 BFS 验证在限制条件下能否到达终点。二分 DP当判定本身具有一定动态规划性质时check 里可能要跑一个线性 DP。整体复杂度可能会变成 O(n log C)在数据范围较小时也能接受。这些变形看似复杂但核心永远是那三步定区间、写 check、套模板。你只要练熟基础的两三种 check 写法遇到变种题时就多了一分底气和从容。说一个我自己的体会二分答案这种题最大的难度不是代码而是你敢不敢往这个方向想。很多同学看到最大值最小的第一反应是动态规划或者某些高级数据结构结果绕了远路。我的建议是做蓝桥杯历年题目的时候凡是有最大值最小最小值最大最多/最少能拿多少这类字眼先把二分答案写一版再想其他解法。很多时候二分答案版的代码是你所有解法里最短最稳的那一个。最后再分享一个小技巧如果你在赛场上碰到一道题完全没有思路但答案形式是求某个量的最大/最小值而且你可以判断它出现在一个有限区间里不妨试试二分答案——哪怕 check 写得粗糙一点至少能拿到一部分测试点的分数。这个思路在比赛的关键时刻往往能救回一道题的分。