尧图网站开发 
刷算法题这几年二分答案算是我最常用也最愿意给新人讲的技巧之一。它不需要像线段树那样背一长串模板也不需要很强的数学推导能力只要你能判断出一道题的答案具有“单调性”再写一个不算太复杂的check函数就能把很多“求最优解”的难题悄悄变成“判断某个值行不行”的简单题。市面上的二分答案文章很多但大多是讲完概念直接甩模板真正用两个经典题目把“什么时候用、怎么设计check、边界怎么调、错在哪”串起来的少之又少。这篇文章我就用两道题来把整个流程走一遍一道是POJ 2456进击的奶牛属于典型的“最小值最大化”另一道是洛谷P1182数列分段 Section II属于典型的“最大值最小化”。两道题练透之后你会发现二分答案其实就是一套固定动作——先确认单调性再写check最后套二分框架。1. 二分答案动手写代码前先想清楚这四件事1.1 二分答案到底是什么和普通二分有什么区别很多人口中的“二分”第一反应是在一个有序数组里找一个数比如在[1, 3, 5, 7, 9]里找7每次取中间位置比较大小后砍掉一半区间最终定位到目标元素。这个经典的查找场景二分的是“数组下标”或“元素本身”。而二分答案完全换了个对象它二分的是一个“答案的取值范围”。什么意思呢假设题目最终要你输出一个整数ans并且这个ans一定落在[L, R]这个区间里同时对于任意一个候选值x你都能快速回答“答案能不能不超过x”或者“答案能不能至少是x”那么你就可以在这个值域上做二分搜索不断缩小答案可能的范围最后逼出最优解。这个过程看起来和查找很像但思维角度完全不同。普通二分是“东西已经摆好了我去定位它的位置”二分答案是“结果是一个神秘数字我通过不断试探来缩小它的藏身范围”。很多初学者一开始转不过弯就是因为还在用“查找”的眼光看待它。我建议你把二分答案理解成一场“读数游戏”我手里有个数字你每次猜一个数我只回答“对了”“小了”还是“大了”你通过每次的回答把范围折半很快就猜中。check函数就是那台判断“大了还是小了”的机器。1.2 能用二分答案的题都有一个共同标志单调性不是所有求最优解的题都能用二分答案。能用它的前提是check函数的结果必须随x单调变化。我举个例子来感受。假设你从起点出发每次给你一个“单次能走的距离限制d”判断你能否在步数限制内走到终点。显然d越大你能走的步数越少到达终点的可能性就越高d越小你越容易把自己憋死在半路。于是“能否走到终点”这个判断结果会随着d的增大从false变成true在这个变化过程中一定存在一个临界值它就是“满足条件的最短单次距离”。如果题目让你求的就是这个临界值恭喜你这是一个典型的二分答案题。我刚才说“从false变成true”或者反过来“从true变成false”这其实就是单调性的两种方向。在进击的奶牛题里“两头牛之间的最小距离不小于d”这个条件当d变大时越来越难满足所以check(d)从true逐渐变成false而在数列分段题里“每段和的最大值不超过x”这个条件当x变大时越来越容易满足所以check(x)从false逐渐变成true。你不需要把“单调性”这个词想得多玄乎你只需要问自己一句话我猜的那个答案如果变大判断结果是不是只会往一个方向倒如果是这个题就能二分如果不是请立刻放弃二分去想别的算法。1.3 二分答案的通用模板我推荐你只记这一种网上关于二分的写法五花八门有while (l r)加上mid (l r 1) 1的也有while (l r)直接记录答案的。我在带新人时强烈建议统一用一种写法就是while (l r)配合mid (l r) 1在check为true时记录一下当前答案。它的好处是思路最直白不容易死循环最后答案也能稳稳落在一个变量里。// 以“正整数值域上求满足条件的最小值”为例 while (l r) { int mid (l r) 1; if (check(mid)) { // 满足条件 ans mid; // 记录当前可行答案 r mid - 1; // 尝试找更小的可行值 } else { l mid 1; // mid太小必须往大走 } } cout ans endl;如果一个题是求最大值只需要把r mid - 1和l mid 1这两句换位置思路是mid可行就尝试更大所以l mid 1并记录mid不可行就说明太大了所以r mid - 1。下一章的两道题我全部用这一种模板来做。在使用这个模板的时候还有两个小细节要提前说好。第一个是mid (l r) 1在C里等价于向下取整如果l r是负数会出问题但二分答案的值域几乎都是正数不需要担心。第二个是注意l和r的初始值不要乱设不要拍脑袋写l 0, r 1e9而是尽量从题目数据本身推出来这样既快又不容易出错后面我会专门讲怎么定上下界。2. 第一道题进击的奶牛把“最小值最大化”一次做透2.1 题意与建模请把每头牛想象成占位符先来读题。农夫约翰有一排牛棚这些牛棚分布在坐标轴的不同位置上数量是N现在要把C头牛安排进这些牛棚里住。牛有个毛病离得太近就会打架所以农夫希望任意两头牛之间的距离都尽量大。注意题目求的不是“所有距离都最大的方案”而是“在某种放法下任意两头牛之间的最小距离最大能是多少”这就是典型的“最小值最大化”问题。你可以这样理解我们想尽量让牛之间住得散一些但是最挤的那一对决定了整个方案的底线。题目问的是这个底线的最大值。比如牛棚在位置2、5、9放3头牛如果放在2和5最近距离是3放在2和9最近距离是7放在5和9最近距离是4。显然最优方案是2和9最小距离是7但真实题目里牛棚更多手动枚举根本不可能所以必须靠算法去找。为什么这道题能二分呢因为“最小距离”本身是一个范围很大的整数变量它最小可以是0两头牛挤同一个棚虽然题目一般不允许最大可以是a[N-1] - a[0]也就是把所有牛棚都用了也会超过这个值。在这个范围内任意取一个候选距离d我都能用一个很简单的模拟方法判断“能不能放下C头牛”而且d越大越难放下具备单调性天然适合二分。2.2 二分的上下界怎么定别再用1e9偷懒很多新手写二分答案特别喜欢写l 0, r 999999999感觉这样“一定能覆盖答案”。但这种写法有两个问题一是可能把范围扩得太大导致二分要多跑好几轮虽然log级别的差距不大在部分卡常的题目里会很难受二是范围过大容易让人忽略答案的真实区间一旦思维发散检查逻辑时就不聚焦了。正确做法是从输入数据里直接推导。这道题里答案最小是1因为两头牛不可能在同一个坐标值上而且它们之间的最小距离至少是1如果坐标允许0那你有0个单位的距离就没意义因为题目求的是“最短距离的最大化”距离为0显然不是最优。最大就是排序后最后一个坐标 - 第一个坐标因为就算只放2头牛能拉开的距离也不会超过整个坐标轴的跨度。于是l 1, r a[n - 1] - a[0]这个范围既不会漏答案又贴合数据。这里有个很关键的小提示一定要先把牛棚坐标排序因为牛棚是沿着一条直线分布的题目给的顺序可能是乱的。如果不排序后面的贪心放牛过程完全无法进行。每次二分判断时你本质上是在一个有序数组里决定“能不能用距离间隔d从第一个棚开始放满C头牛”。2.3 check函数贪心地从头往后放绝不回头二分答案的check函数往往是整个题的核心难点。好在进击的奶牛这道题的check比较直观已知牛棚坐标从小到大排好序又已知你要保证任意两头牛之间的距离不小于d那么最优策略一定是“第一头牛放在最左边的牛棚之后每次遇到一个与上一头牛所在棚的距离至少为d的棚就立刻放下一头牛”。为什么这个贪心策略是对的因为最左边的牛棚离所有其他牛棚都最远从它开始放不会让任何约束变得更苛刻。而每次遇到一个满足“距离≥d”的棚就立刻放下牛也保证了后续所有牛棚离当前这头牛的距离是最宽松的给后面的牛留下了最大的空间。如果你非要跳过某个符合条件的棚放得更远那只会白白浪费中间的可利用空间结果不可能更好。check函数的代码写出来就是bool check(long long d) { int cnt 1; // 第一头牛放在第一个牛棚 long long last a[0]; // 上一头牛所在位置 for (int i 1; i n; i) { if (a[i] - last d) { // 当前位置能和上一头牛保持至少d的距离 cnt; last a[i]; if (cnt c) return true; // 已经放下C头牛提前退出 } } return cnt c; }这里你可以看到check函数本身的时间复杂度是O(N)而整个二分的复杂度是O(log(范围) * N)。在N达到10万甚至更大时这个复杂度完全扛得住这也是二分答案最大的优势之一——用一次O(N)的模拟去换掉原本可能O(N^2)甚至更爆炸的枚举。2.4 完整代码与关键注释把前面所有部分拼起来搭配标准的二分框架完整代码就是这样的#include bits/stdc.h using namespace std; int n, c; vectorlong long a; bool check(long long d) { int cnt 1; long long last a[0]; for (int i 1; i n; i) { if (a[i] - last d) { cnt; last a[i]; if (cnt c) return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n c; a.resize(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long l 1, r a[n - 1] - a[0]; long long ans 0; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; // 当前距离d可行尝试更大距离 l mid 1; } else { r mid - 1; // 当前距离d放不下C头牛必须缩小距离 } } cout ans endl; return 0; }当check(mid)返回true时说明“至少间隔mid”仍然能放下C头牛所以答案至少是mid我们就往更大的方向去找当返回false时说明mid太大了必须往小的方向收。循环结束后ans里存的就是最后一个可行的mid也就是答案。这里值得注意我专门用一个ans变量来记录答案而不是最后输出r或l原因是l和r在循环结束时已经错位直接输出容易记混哪个是答案新手极容易写错有ans在手就稳了。2.5 这道题最容易踩的三个坑第一个坑check的单调方向写反。有的同学会把“check(mid)为true时往左收缩”结果答案越找越小。这里我建议你每次写完check后顺手拿两个极端的例子验一下比如检查d1时放牛肯定能成d跨度时八成不成看看返回是否符合直觉。第二个坑排序写漏。牛棚坐标不是按顺序给的很多新人写check函数时默认数组有序结果样例一过就交后面WA到怀疑人生。二分答案题里凡是涉及坐标、位置、区间的东西第一件事就是排序。第三个坑整数运算溢出。坐标范围可能到1e9N到1e5a[i] - last别用int存mid计算时(l r) 1的lr也可能超int范围。我的建议是一律开long long省得到时候排查溢出问题。3. 第二道题数列分段把“最大值最小化”逆向打通3.1 题意与建模把一列数切成M段让最重的那段尽量轻再看第二道题给定一个长度为N的正整数数列要求把它切成连续的M段问这M段中每一段数字的和的最大值最小可以是多少。用大白话说就是把这串数字分成M组每组必须是连续的一段这些组的“总重量”参差不齐但最重的那组决定了你的方案的“上限”我们要让这个上限越小越好。你可以想象成把一段绳子切成M小段每小段上挂着一串砝码你希望最累的那小段绳子承受的重量尽量小。比如数列[4, 2, 4, 5, 1]分成3段如果切法是[4,2] [4,5] [1]三段和分别是6、9、1最大值是9如果换成[4] [2,4] [5,1]三段和是4、6、6最大值是6比9小很多。题目求的就是这个最小可能的最大值。这道题和上一道正好是“对偶”的关系上一道是在约束里尽量拉开距离这一道是在约束里尽量压扁上限上一道是“最小值最大化”这一道是“最大值最小化”。如果你能把这套题彻底搞明白那么一大半二分答案题对你来说都只是换皮。3.2 二分到底在二分什么为什么下界不能从1开始数列分段这个题我们要二分的不是“某个位置”而是“每段和的上限x”。什么意思呢我猜一个数x假装“每段和都不能超过x”然后看在这种限制下能不能用不超过M段把数列切完。如果能切完就说明x是可行的但它可能还有下调空间如果不能切完就说明x太小了给每段分配的“重量预算”不够必须提高x。上下界怎么定答案的下界不是1而是整个数列中最大的那个元素。因为不管怎么分段单独一个元素自己也算一段如果x比某个元素还小那这个元素无论塞到哪一段该段的和都会超过x所以必不可能成功。上界则简单很多把所有元素的和当成上界因为把所有数合成一整段这一段的和就是总和无论如何也不会超过它。这种“用数据本身推导上下界”的习惯我建议你从这道题开始养成。你看下界是max(A[i])上界是sum(A)这两个值在输入时顺手就算完了根本不需要灵光乍现或者硬编码一个超大数既准确又高效。3.3 check函数一趟贪心就能数出最少要切几段接下来是核心给定上限x如何判断“能否用不超过M段完成任务”这里同样用贪心。我们从左往右扫过数列用一个变量cur记录当前这一段已经累加的和。每当要加入一个新元素时先判断“cur 这个元素是否超过x”。如果没超过就把这个元素塞进当前段如果超过了就说明当前段已经装满了必须先把这一段“封口”然后从当前元素开始开新的一段。bool check(long long x) { long long cur 0; int seg 1; // 至少会有一整段 for (int i 1; i n; i) { if (cur a[i] x) { seg; // 当前段装不下必须从a[i]重新开一段 cur a[i]; } else { cur a[i]; } } return seg m; }为什么这个贪心是对的因为我们想让段数尽量少而段数少意味着“尽可能把元素塞进现有段里”只有实在塞不下才被迫开新段。这个策略保证了在同样的x限制下切出来的段数是最少的。于是check的逻辑就变成了在最理想的情况下我切出来的段数都不超过M那说明x可行如果连“尽量少切”都超过M了那x就肯定不够用。这里有个细节要跟新手强调题面说的是“分成M段”但check返回的是seg m不是seg m。原因很简单如果你在贪心战略下切出来的段数是3段而题目要求5段你完全可以把其中一段再切开比如一段和是10切成两个5段数变多但每段和还是不超过x。所以“最少的段数都能控制在M以内”那就一定存在合法方案反过来如果最少的段数都比M大那其他任何切法都不可能让段数变少方案必然不存在。3.4 完整代码与运行效果整合成完整可运行的代码如下所示#include bits/stdc.h using namespace std; int n, m; vectorlong long a; bool check(long long x) { long long cur 0; int seg 1; for (int i 1; i n; i) { if (cur a[i] x) { seg; cur a[i]; } else { cur a[i]; } } return seg m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; a.resize(n 1); long long l 0, r 0; for (int i 1; i n; i) { cin a[i]; r a[i]; l max(l, a[i]); } while (l r) { long long mid (l r) 1; if (check(mid)) { r mid - 1; // 上限mid可行尝试更小的上限 } else { l mid 1; // 上限mid太小必须放大 } } cout l endl; return 0; }注意这道题的二分方向和上一道正好相反当check(mid)为true说明x还有可能更小于是我们把右边界往左收也就是r mid - 1当check为false说明上限太紧必须往右扩大也就是l mid 1。循环结束后l指向的就是“第一个满足条件”的值也就是最小的可行上限正好是答案。3.5 两道题一对比方向就彻底清楚了我把这两道题的核心参数放到一张表里你盯着看十秒钟就能记住二分答案的方向规律。对比项例1进击的奶牛例2数列分段所求类型最小值最大化最大值最小化二分对象最小距离d每段和的上限x单调性d越大越难放下C头牛x越大越容易分成不超过M段check策略贪心放牛统计能放几头贪心分段统计最少切几段check(mid)为真时答案至少mid试探更大 → lmid1答案可能更小试探更小 → rmid-1最终输出ans记录最后一个可行的midl第一个可行的mid看到没只要你确认了“check(mid)为真意味着什么”二分方向就永远不会搞反。在这两道题里check为真分别意味着“当前值可行想再贪心一点”和“当前值可行想再压缩一点”方向完全相反但背后的逻辑链条是同一条。这就是我说“两道题练透二分答案就通了”的原因。4. 常见问题与排查技巧实录4.1 检查结果不对先别改模板先查这三处我见过太多人二分答案WA了第一反应是“模板是不是记错了”其实九成问题都出在check函数或边界上。你要是有这个功夫不如按这三个步骤排查先打印一组极端的mid看看check返回是否符合直觉。比如进击的奶牛题里你打印check(1)应该必然truecheck(跨度)应该是false如果反了说明单调方向写反或者check条件写反了。接着查看上下界确认下界有没有设置过低或过高尤其是“最小值最大化”题里下界若是0而上界又恰好比较小答案确实可能是0但很多时候答案根本不可能是0设成0反而掩盖了真实区间。最后仔细看你check函数里的循环范围确认有没有越界或者漏掉第一个元素。我教过不少学生最后的bug都是for (int i 1; i n; i)写成了i n数组访问越界答案自然乱七八糟。4.2 死循环是怎么来的为什么我让你统一用while(lr)二分答案最让人头疼的就是死循环。死循环的根源通常是while (l r)配合mid (l r) 1时当l和r相邻mid会等于l而如果你写的逻辑是“不可行时l mid”那l永远卡在原地循环就转不出去。反过来如果你用while (l r)配合mid (l r 1) 1在某种逻辑下也可能卡在r上。我用while (l r)加记录答案的写法就是为了从根上避免这类死循环。循环条件是l r每一次迭代l和r都必然有一方会跨过mid区间范围严格缩小循环一定会结束。并且答案通过ans变量保存不依赖最后l和r的指向彻底避开“该输出l还是r”的疑惑。如果你已经习惯了别的模板我也建议你在写题时固定用一种不要这次用这个模板、下次用那个模板脚踩两条船最容易翻车。4.3 如果题目答案是小数怎么办实数域二分的两个要点有些二分答案题答案不是整数比如切绳子、求水位高度、求速度最大值这时同样的思想依然适用只是需要处理精度。最常见的方法是设置一个足够小的eps比如while (r - l 1e-7)或者直接固定迭代100次因为二分每轮都能缩短一半区间做100次足以把精度压到极小。实数域上要注意两点第一mid (l r) / 2.0别手滑写成整数除法第二check函数里所有中间变量也要用double千万不要把浮点数和整数混着算否则精度白给。还有一个实用小技巧如果你不确定eps该设多少可以按题目要求的输出精度再往下取两个数量级比如题目要求保留6位小数你就用1e-8这样即使有小幅误差也不容易出问题。当然如果数据允许也可以把所有值都乘以一个缩放系数转成整数再二分我一向更喜欢这样做因为整数二分能彻底避开浮点精度问题。4.4 进阶二分答案还能和哪些算法组合使用很多新手以为二分答案的check函数只能配合贪心其实它的想象空间远不止于此。我见过且亲自做过的组合就有好几种check里用前缀和快速判断一个区间的和是否满足限制配合二分求“平均值最大的连续子段”check里用DP或背包思想判断当前限制能不能在不超时的前提下达到目标check里甚至还能套二分图匹配比如给每个任务分配一个不低于阈值的分数判断N个任务能否两两配对成功。每一种组合都能撑起一类题型。所以你可以把二分答案理解成一把“万能钥匙”它能开的锁的种类完全取决于你会写什么样的check函数。我的建议是先把今天这两道题的贪心check练到闭眼能写再去找几道带前缀和的、带DP的二分答案题练手。你会发现二分答案本身不是难点难点永远在于“给定一个值你能不能设计出一个高效的判定方法”而这只能靠多见识题型来积累。我个人练下来最大的感受是二分答案真正带给我的不是模板而是一种条件反射一看到“最大值最小”“最小值最大”“最短的尽量长”“最长的尽量短”这类描述我脑子里会立刻弹出一句话——能不能写个check试试很多时候check比二分本身要难但只要你把check写出来这个题就已经解决了大半。最后再分享一个小技巧调试二分答案题的时候别只盯着mid的取值多打印几个关键边界值比如ans-1、ans、ans1各自对应的check结果一眼就能看出你是单调方向写反了还是边界范围没卡准。希望这两道题这篇文章能让你以后遇到二分答案也像我一样先笑出声来。 
刷算法题这几年二分答案算是我最常用也最愿意给新人讲的技巧之一。它不需要像线段树那样背一长串模板也不需要很强的数学推导能力只要你能判断出一道题的答案具有“单调性”再写一个不算太复杂的check函数就能把很多“求最优解”的难题悄悄变成“判断某个值行不行”的简单题。市面上的二分答案文章很多但大多是讲完概念直接甩模板真正用两个经典题目把“什么时候用、怎么设计check、边界怎么调、错在哪”串起来的少之又少。这篇文章我就用两道题来把整个流程走一遍一道是POJ 2456进击的奶牛属于典型的“最小值最大化”另一道是洛谷P1182数列分段 Section II属于典型的“最大值最小化”。两道题练透之后你会发现二分答案其实就是一套固定动作——先确认单调性再写check最后套二分框架。1. 二分答案动手写代码前先想清楚这四件事1.1 二分答案到底是什么和普通二分有什么区别很多人口中的“二分”第一反应是在一个有序数组里找一个数比如在[1, 3, 5, 7, 9]里找7每次取中间位置比较大小后砍掉一半区间最终定位到目标元素。这个经典的查找场景二分的是“数组下标”或“元素本身”。而二分答案完全换了个对象它二分的是一个“答案的取值范围”。什么意思呢假设题目最终要你输出一个整数ans并且这个ans一定落在[L, R]这个区间里同时对于任意一个候选值x你都能快速回答“答案能不能不超过x”或者“答案能不能至少是x”那么你就可以在这个值域上做二分搜索不断缩小答案可能的范围最后逼出最优解。这个过程看起来和查找很像但思维角度完全不同。普通二分是“东西已经摆好了我去定位它的位置”二分答案是“结果是一个神秘数字我通过不断试探来缩小它的藏身范围”。很多初学者一开始转不过弯就是因为还在用“查找”的眼光看待它。我建议你把二分答案理解成一场“读数游戏”我手里有个数字你每次猜一个数我只回答“对了”“小了”还是“大了”你通过每次的回答把范围折半很快就猜中。check函数就是那台判断“大了还是小了”的机器。1.2 能用二分答案的题都有一个共同标志单调性不是所有求最优解的题都能用二分答案。能用它的前提是check函数的结果必须随x单调变化。我举个例子来感受。假设你从起点出发每次给你一个“单次能走的距离限制d”判断你能否在步数限制内走到终点。显然d越大你能走的步数越少到达终点的可能性就越高d越小你越容易把自己憋死在半路。于是“能否走到终点”这个判断结果会随着d的增大从false变成true在这个变化过程中一定存在一个临界值它就是“满足条件的最短单次距离”。如果题目让你求的就是这个临界值恭喜你这是一个典型的二分答案题。我刚才说“从false变成true”或者反过来“从true变成false”这其实就是单调性的两种方向。在进击的奶牛题里“两头牛之间的最小距离不小于d”这个条件当d变大时越来越难满足所以check(d)从true逐渐变成false而在数列分段题里“每段和的最大值不超过x”这个条件当x变大时越来越容易满足所以check(x)从false逐渐变成true。你不需要把“单调性”这个词想得多玄乎你只需要问自己一句话我猜的那个答案如果变大判断结果是不是只会往一个方向倒如果是这个题就能二分如果不是请立刻放弃二分去想别的算法。1.3 二分答案的通用模板我推荐你只记这一种网上关于二分的写法五花八门有while (l r)加上mid (l r 1) 1的也有while (l r)直接记录答案的。我在带新人时强烈建议统一用一种写法就是while (l r)配合mid (l r) 1在check为true时记录一下当前答案。它的好处是思路最直白不容易死循环最后答案也能稳稳落在一个变量里。// 以“正整数值域上求满足条件的最小值”为例 while (l r) { int mid (l r) 1; if (check(mid)) { // 满足条件 ans mid; // 记录当前可行答案 r mid - 1; // 尝试找更小的可行值 } else { l mid 1; // mid太小必须往大走 } } cout ans endl;如果一个题是求最大值只需要把r mid - 1和l mid 1这两句换位置思路是mid可行就尝试更大所以l mid 1并记录mid不可行就说明太大了所以r mid - 1。下一章的两道题我全部用这一种模板来做。在使用这个模板的时候还有两个小细节要提前说好。第一个是mid (l r) 1在C里等价于向下取整如果l r是负数会出问题但二分答案的值域几乎都是正数不需要担心。第二个是注意l和r的初始值不要乱设不要拍脑袋写l 0, r 1e9而是尽量从题目数据本身推出来这样既快又不容易出错后面我会专门讲怎么定上下界。2. 第一道题进击的奶牛把“最小值最大化”一次做透2.1 题意与建模请把每头牛想象成占位符先来读题。农夫约翰有一排牛棚这些牛棚分布在坐标轴的不同位置上数量是N现在要把C头牛安排进这些牛棚里住。牛有个毛病离得太近就会打架所以农夫希望任意两头牛之间的距离都尽量大。注意题目求的不是“所有距离都最大的方案”而是“在某种放法下任意两头牛之间的最小距离最大能是多少”这就是典型的“最小值最大化”问题。你可以这样理解我们想尽量让牛之间住得散一些但是最挤的那一对决定了整个方案的底线。题目问的是这个底线的最大值。比如牛棚在位置2、5、9放3头牛如果放在2和5最近距离是3放在2和9最近距离是7放在5和9最近距离是4。显然最优方案是2和9最小距离是7但真实题目里牛棚更多手动枚举根本不可能所以必须靠算法去找。为什么这道题能二分呢因为“最小距离”本身是一个范围很大的整数变量它最小可以是0两头牛挤同一个棚虽然题目一般不允许最大可以是a[N-1] - a[0]也就是把所有牛棚都用了也会超过这个值。在这个范围内任意取一个候选距离d我都能用一个很简单的模拟方法判断“能不能放下C头牛”而且d越大越难放下具备单调性天然适合二分。2.2 二分的上下界怎么定别再用1e9偷懒很多新手写二分答案特别喜欢写l 0, r 999999999感觉这样“一定能覆盖答案”。但这种写法有两个问题一是可能把范围扩得太大导致二分要多跑好几轮虽然log级别的差距不大在部分卡常的题目里会很难受二是范围过大容易让人忽略答案的真实区间一旦思维发散检查逻辑时就不聚焦了。正确做法是从输入数据里直接推导。这道题里答案最小是1因为两头牛不可能在同一个坐标值上而且它们之间的最小距离至少是1如果坐标允许0那你有0个单位的距离就没意义因为题目求的是“最短距离的最大化”距离为0显然不是最优。最大就是排序后最后一个坐标 - 第一个坐标因为就算只放2头牛能拉开的距离也不会超过整个坐标轴的跨度。于是l 1, r a[n - 1] - a[0]这个范围既不会漏答案又贴合数据。这里有个很关键的小提示一定要先把牛棚坐标排序因为牛棚是沿着一条直线分布的题目给的顺序可能是乱的。如果不排序后面的贪心放牛过程完全无法进行。每次二分判断时你本质上是在一个有序数组里决定“能不能用距离间隔d从第一个棚开始放满C头牛”。2.3 check函数贪心地从头往后放绝不回头二分答案的check函数往往是整个题的核心难点。好在进击的奶牛这道题的check比较直观已知牛棚坐标从小到大排好序又已知你要保证任意两头牛之间的距离不小于d那么最优策略一定是“第一头牛放在最左边的牛棚之后每次遇到一个与上一头牛所在棚的距离至少为d的棚就立刻放下一头牛”。为什么这个贪心策略是对的因为最左边的牛棚离所有其他牛棚都最远从它开始放不会让任何约束变得更苛刻。而每次遇到一个满足“距离≥d”的棚就立刻放下牛也保证了后续所有牛棚离当前这头牛的距离是最宽松的给后面的牛留下了最大的空间。如果你非要跳过某个符合条件的棚放得更远那只会白白浪费中间的可利用空间结果不可能更好。check函数的代码写出来就是bool check(long long d) { int cnt 1; // 第一头牛放在第一个牛棚 long long last a[0]; // 上一头牛所在位置 for (int i 1; i n; i) { if (a[i] - last d) { // 当前位置能和上一头牛保持至少d的距离 cnt; last a[i]; if (cnt c) return true; // 已经放下C头牛提前退出 } } return cnt c; }这里你可以看到check函数本身的时间复杂度是O(N)而整个二分的复杂度是O(log(范围) * N)。在N达到10万甚至更大时这个复杂度完全扛得住这也是二分答案最大的优势之一——用一次O(N)的模拟去换掉原本可能O(N^2)甚至更爆炸的枚举。2.4 完整代码与关键注释把前面所有部分拼起来搭配标准的二分框架完整代码就是这样的#include bits/stdc.h using namespace std; int n, c; vectorlong long a; bool check(long long d) { int cnt 1; long long last a[0]; for (int i 1; i n; i) { if (a[i] - last d) { cnt; last a[i]; if (cnt c) return true; } } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n c; a.resize(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long l 1, r a[n - 1] - a[0]; long long ans 0; while (l r) { long long mid (l r) 1; if (check(mid)) { ans mid; // 当前距离d可行尝试更大距离 l mid 1; } else { r mid - 1; // 当前距离d放不下C头牛必须缩小距离 } } cout ans endl; return 0; }当check(mid)返回true时说明“至少间隔mid”仍然能放下C头牛所以答案至少是mid我们就往更大的方向去找当返回false时说明mid太大了必须往小的方向收。循环结束后ans里存的就是最后一个可行的mid也就是答案。这里值得注意我专门用一个ans变量来记录答案而不是最后输出r或l原因是l和r在循环结束时已经错位直接输出容易记混哪个是答案新手极容易写错有ans在手就稳了。2.5 这道题最容易踩的三个坑第一个坑check的单调方向写反。有的同学会把“check(mid)为true时往左收缩”结果答案越找越小。这里我建议你每次写完check后顺手拿两个极端的例子验一下比如检查d1时放牛肯定能成d跨度时八成不成看看返回是否符合直觉。第二个坑排序写漏。牛棚坐标不是按顺序给的很多新人写check函数时默认数组有序结果样例一过就交后面WA到怀疑人生。二分答案题里凡是涉及坐标、位置、区间的东西第一件事就是排序。第三个坑整数运算溢出。坐标范围可能到1e9N到1e5a[i] - last别用int存mid计算时(l r) 1的lr也可能超int范围。我的建议是一律开long long省得到时候排查溢出问题。3. 第二道题数列分段把“最大值最小化”逆向打通3.1 题意与建模把一列数切成M段让最重的那段尽量轻再看第二道题给定一个长度为N的正整数数列要求把它切成连续的M段问这M段中每一段数字的和的最大值最小可以是多少。用大白话说就是把这串数字分成M组每组必须是连续的一段这些组的“总重量”参差不齐但最重的那组决定了你的方案的“上限”我们要让这个上限越小越好。你可以想象成把一段绳子切成M小段每小段上挂着一串砝码你希望最累的那小段绳子承受的重量尽量小。比如数列[4, 2, 4, 5, 1]分成3段如果切法是[4,2] [4,5] [1]三段和分别是6、9、1最大值是9如果换成[4] [2,4] [5,1]三段和是4、6、6最大值是6比9小很多。题目求的就是这个最小可能的最大值。这道题和上一道正好是“对偶”的关系上一道是在约束里尽量拉开距离这一道是在约束里尽量压扁上限上一道是“最小值最大化”这一道是“最大值最小化”。如果你能把这套题彻底搞明白那么一大半二分答案题对你来说都只是换皮。3.2 二分到底在二分什么为什么下界不能从1开始数列分段这个题我们要二分的不是“某个位置”而是“每段和的上限x”。什么意思呢我猜一个数x假装“每段和都不能超过x”然后看在这种限制下能不能用不超过M段把数列切完。如果能切完就说明x是可行的但它可能还有下调空间如果不能切完就说明x太小了给每段分配的“重量预算”不够必须提高x。上下界怎么定答案的下界不是1而是整个数列中最大的那个元素。因为不管怎么分段单独一个元素自己也算一段如果x比某个元素还小那这个元素无论塞到哪一段该段的和都会超过x所以必不可能成功。上界则简单很多把所有元素的和当成上界因为把所有数合成一整段这一段的和就是总和无论如何也不会超过它。这种“用数据本身推导上下界”的习惯我建议你从这道题开始养成。你看下界是max(A[i])上界是sum(A)这两个值在输入时顺手就算完了根本不需要灵光乍现或者硬编码一个超大数既准确又高效。3.3 check函数一趟贪心就能数出最少要切几段接下来是核心给定上限x如何判断“能否用不超过M段完成任务”这里同样用贪心。我们从左往右扫过数列用一个变量cur记录当前这一段已经累加的和。每当要加入一个新元素时先判断“cur 这个元素是否超过x”。如果没超过就把这个元素塞进当前段如果超过了就说明当前段已经装满了必须先把这一段“封口”然后从当前元素开始开新的一段。bool check(long long x) { long long cur 0; int seg 1; // 至少会有一整段 for (int i 1; i n; i) { if (cur a[i] x) { seg; // 当前段装不下必须从a[i]重新开一段 cur a[i]; } else { cur a[i]; } } return seg m; }为什么这个贪心是对的因为我们想让段数尽量少而段数少意味着“尽可能把元素塞进现有段里”只有实在塞不下才被迫开新段。这个策略保证了在同样的x限制下切出来的段数是最少的。于是check的逻辑就变成了在最理想的情况下我切出来的段数都不超过M那说明x可行如果连“尽量少切”都超过M了那x就肯定不够用。这里有个细节要跟新手强调题面说的是“分成M段”但check返回的是seg m不是seg m。原因很简单如果你在贪心战略下切出来的段数是3段而题目要求5段你完全可以把其中一段再切开比如一段和是10切成两个5段数变多但每段和还是不超过x。所以“最少的段数都能控制在M以内”那就一定存在合法方案反过来如果最少的段数都比M大那其他任何切法都不可能让段数变少方案必然不存在。3.4 完整代码与运行效果整合成完整可运行的代码如下所示#include bits/stdc.h using namespace std; int n, m; vectorlong long a; bool check(long long x) { long long cur 0; int seg 1; for (int i 1; i n; i) { if (cur a[i] x) { seg; cur a[i]; } else { cur a[i]; } } return seg m; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; a.resize(n 1); long long l 0, r 0; for (int i 1; i n; i) { cin a[i]; r a[i]; l max(l, a[i]); } while (l r) { long long mid (l r) 1; if (check(mid)) { r mid - 1; // 上限mid可行尝试更小的上限 } else { l mid 1; // 上限mid太小必须放大 } } cout l endl; return 0; }注意这道题的二分方向和上一道正好相反当check(mid)为true说明x还有可能更小于是我们把右边界往左收也就是r mid - 1当check为false说明上限太紧必须往右扩大也就是l mid 1。循环结束后l指向的就是“第一个满足条件”的值也就是最小的可行上限正好是答案。3.5 两道题一对比方向就彻底清楚了我把这两道题的核心参数放到一张表里你盯着看十秒钟就能记住二分答案的方向规律。对比项例1进击的奶牛例2数列分段所求类型最小值最大化最大值最小化二分对象最小距离d每段和的上限x单调性d越大越难放下C头牛x越大越容易分成不超过M段check策略贪心放牛统计能放几头贪心分段统计最少切几段check(mid)为真时答案至少mid试探更大 → lmid1答案可能更小试探更小 → rmid-1最终输出ans记录最后一个可行的midl第一个可行的mid看到没只要你确认了“check(mid)为真意味着什么”二分方向就永远不会搞反。在这两道题里check为真分别意味着“当前值可行想再贪心一点”和“当前值可行想再压缩一点”方向完全相反但背后的逻辑链条是同一条。这就是我说“两道题练透二分答案就通了”的原因。4. 常见问题与排查技巧实录4.1 检查结果不对先别改模板先查这三处我见过太多人二分答案WA了第一反应是“模板是不是记错了”其实九成问题都出在check函数或边界上。你要是有这个功夫不如按这三个步骤排查先打印一组极端的mid看看check返回是否符合直觉。比如进击的奶牛题里你打印check(1)应该必然truecheck(跨度)应该是false如果反了说明单调方向写反或者check条件写反了。接着查看上下界确认下界有没有设置过低或过高尤其是“最小值最大化”题里下界若是0而上界又恰好比较小答案确实可能是0但很多时候答案根本不可能是0设成0反而掩盖了真实区间。最后仔细看你check函数里的循环范围确认有没有越界或者漏掉第一个元素。我教过不少学生最后的bug都是for (int i 1; i n; i)写成了i n数组访问越界答案自然乱七八糟。4.2 死循环是怎么来的为什么我让你统一用while(lr)二分答案最让人头疼的就是死循环。死循环的根源通常是while (l r)配合mid (l r) 1时当l和r相邻mid会等于l而如果你写的逻辑是“不可行时l mid”那l永远卡在原地循环就转不出去。反过来如果你用while (l r)配合mid (l r 1) 1在某种逻辑下也可能卡在r上。我用while (l r)加记录答案的写法就是为了从根上避免这类死循环。循环条件是l r每一次迭代l和r都必然有一方会跨过mid区间范围严格缩小循环一定会结束。并且答案通过ans变量保存不依赖最后l和r的指向彻底避开“该输出l还是r”的疑惑。如果你已经习惯了别的模板我也建议你在写题时固定用一种不要这次用这个模板、下次用那个模板脚踩两条船最容易翻车。4.3 如果题目答案是小数怎么办实数域二分的两个要点有些二分答案题答案不是整数比如切绳子、求水位高度、求速度最大值这时同样的思想依然适用只是需要处理精度。最常见的方法是设置一个足够小的eps比如while (r - l 1e-7)或者直接固定迭代100次因为二分每轮都能缩短一半区间做100次足以把精度压到极小。实数域上要注意两点第一mid (l r) / 2.0别手滑写成整数除法第二check函数里所有中间变量也要用double千万不要把浮点数和整数混着算否则精度白给。还有一个实用小技巧如果你不确定eps该设多少可以按题目要求的输出精度再往下取两个数量级比如题目要求保留6位小数你就用1e-8这样即使有小幅误差也不容易出问题。当然如果数据允许也可以把所有值都乘以一个缩放系数转成整数再二分我一向更喜欢这样做因为整数二分能彻底避开浮点精度问题。4.4 进阶二分答案还能和哪些算法组合使用很多新手以为二分答案的check函数只能配合贪心其实它的想象空间远不止于此。我见过且亲自做过的组合就有好几种check里用前缀和快速判断一个区间的和是否满足限制配合二分求“平均值最大的连续子段”check里用DP或背包思想判断当前限制能不能在不超时的前提下达到目标check里甚至还能套二分图匹配比如给每个任务分配一个不低于阈值的分数判断N个任务能否两两配对成功。每一种组合都能撑起一类题型。所以你可以把二分答案理解成一把“万能钥匙”它能开的锁的种类完全取决于你会写什么样的check函数。我的建议是先把今天这两道题的贪心check练到闭眼能写再去找几道带前缀和的、带DP的二分答案题练手。你会发现二分答案本身不是难点难点永远在于“给定一个值你能不能设计出一个高效的判定方法”而这只能靠多见识题型来积累。我个人练下来最大的感受是二分答案真正带给我的不是模板而是一种条件反射一看到“最大值最小”“最小值最大”“最短的尽量长”“最长的尽量短”这类描述我脑子里会立刻弹出一句话——能不能写个check试试很多时候check比二分本身要难但只要你把check写出来这个题就已经解决了大半。最后再分享一个小技巧调试二分答案题的时候别只盯着mid的取值多打印几个关键边界值比如ans-1、ans、ans1各自对应的check结果一眼就能看出你是单调方向写反了还是边界范围没卡准。希望这两道题这篇文章能让你以后遇到二分答案也像我一样先笑出声来。