最近刷 GESP 五级题目的时候碰到一道非常经典的二分答案入门题——luogu P1843 奶牛晒衣服。这题表面看是个模拟题好像模拟每分钟吹干就行了但数据范围一上来模拟直接废掉。真正考的是你能不能想到“二分时间答案 贪心验证”这个套路。今天我把这题从题目解读、思路推导、代码实现到调试过程完整拆一遍顺带讲讲二分答案这类题目的通用解法备考 GESP 五级的同学或者刚开始刷算法题的朋友应该都能用得上。1. 题目速览与考点定位1.1 题面到底在说什么先花两分钟把题意读透。题目大意是有 n 件衣服每件衣服都有一个初始含水量 w[i]。现在有两种干燥方式一种是自然风干每单位时间可以让一件衣服减少 a 的水分另一种是用烘干机每单位时间可以让一件衣服额外减少 b 的水分。注意这里说的是“额外”也就是说烘干机开启时衣服在自然风干的基础上再多减少 b合计每单位时间减少 a b 的水分。问题要求最少需要多长时间才能让所有衣服的含水量降到 0。这里有几个容易读偏的地方。第一烘干机同一时刻只能处理一件衣服它是个串行资源不是你开了之后所有衣服一起受益。第二自然风干是所有衣服同时进行的不占用“额外资源”。第三一件衣服水分降到 0 之后它就不再参与计算了不会出现“干了之后又返潮”这种奇怪情况。理解了这三点题目才算真正读明白。很多新手做这题 WA答案错误不是公式推错而是把“自然风干”和“烘干机”理解成了互斥关系以为用烘干机的时候自然风干就停了那思路从一开始就跑偏了。1.2 这题考的是啥从 GESP 五级的考纲角度看这道题的定位非常精准。五级阶段要求掌握二分查找、贪心算法、递归与分治等核心算法思想。P1843 恰好把二分和贪心结合在一起外层二分枚举时间内层贪心判断可行性。这个组合在 GESP 真题里反复出现在 NOIP、蓝桥杯等比赛里也是基础中的基础。具体来说这题的核心考点有三个层级第一层能不能看出来这题不能用纯模拟做需要二分答案。第二层能不能正确写出 check 函数也就是给定一个时间 t如何判断 t 时间内能否晒干所有衣服。第三层能不能把二分边界、数据类型、向上取整这些细节处理好做到一次 AC。很多同学卡在第二层和第三层之间。check 函数写出来了但边界条件错了或者 long long 没开结果数据一大就爆掉。这些细节恰恰是 GESP 阅卷时最容易扣分的地方。1.3 先定个框架从朴素到二分的思维链条在往下深入之前我想先给整道题搭一个思考框架。我们面对的是“求最短时间”这类问题通常有三条路直接模拟过程一步一步推演直到所有衣服干了为止。顺着“时间越长越容易干”这个直觉把时间当成自变量二分出最小可行值。构造数学模型直接算出答案表达式。第三条路在这题里不容易实现因为每件衣服需要烘干机的时间不能简单合并涉及取整和贪心。第二条路就是正解。第一条路是大多数新手的第一反应但数据一大就必然超时。我建议初学者在看待这道题时先把三种思路在草稿纸上都写一遍再去对比复杂度。这个过程比单纯背代码重要得多因为只有自己踩过“模拟超时”的坑才真正理解二分答案的威力。2. 为什么暴力模拟走不通2.1 最直白的模拟思路长什么样如果你第一次看到这题很自然的想法是开一个循环每分钟让所有衣服自然风干 a 的水分然后选一件最湿的衣服开烘干机让它额外减少 b 的水分等所有衣服含水量都小于等于 0 时输出分钟数。写成伪代码大概是这样的while (true) { // 让所有衣服自然风干 a for (int i 0; i n; i) w[i] - a; // 选一件最湿的衣服用烘干机 int maxIdx 0; for (int i 1; i n; i) { if (w[i] w[maxIdx]) maxIdx i; } w[maxIdx] - b; time; // 判断是否全部干透 bool dry true; for (int i 0; i n; i) { if (w[i] 0) { dry false; break; } } if (dry) break; }说实话这个逻辑本身没什么大毛病小数据下它确实能跑出正确答案。但如果你把这个代码交到 luogu 上结果大概率是 TLE超时。2.2 复杂度分析到底慢在哪我们来算一笔账。假设答案时间是 T那么上面的循环要执行 T 次。每一次循环里要遍历 n 件衣服做自然风干再遍历 n 件找最湿的再遍历 n 件判断是否全部干透单次循环复杂度是 O(n)。整体复杂度就是 O(T·n)。问题在于 T 能有多大。看题目数据范围n 最大可以到 50 万含水量 w[i] 和速度 a、b 也都是很大的整数。最坏情况下如果 a 很小T 可能达到 10^9 级别。O(T·n) 就是 10^9 × 5×10^5 5×10^14 次操作这个量级在普通评测机上跑一天都跑不完。就算你用堆优化每次 O(1) 选最湿的衣服整体复杂度也还是 O(T log n)因为 T 本身可能大到 10^9循环次数依然无法接受。所以这题的瓶颈不在“怎么模拟每一步”而在“怎么避免逐步模拟”。我们要跳出来直接回答一个更宏观的问题给定时间 t能不能干完如果能答案就不超过 t如果不能答案就大于 t。2.3 换个角度搜索答案而不是推演过程模拟思路是“推演过程”而二分思路是“搜索答案”。两者的本质区别在于模拟是在时间轴上一步步走二分是在答案空间里一次次猜。答案空间是什么最短时间一定在 [0, 最大含水量 / 自然风干速度 1] 这个区间内。最坏情况是完全不用烘干机让最湿的那件衣服自然风干到干为止时间就是 max(w[i]) / a可能需要向上取整。在这个区间里我们要找的是“最小的可行时间”。如果你能快速判断一个时间是否可行就可以用二分把判断次数压到 O(log(数据范围))即使范围是 10^9也只需要约 30 次判断。每次判断 O(n)总复杂度 O(n log R)对 50 万的数据来说完全吃得消。这就是二分答案的核心思想把“求最值问题”转化成“可行性判断问题”。后面我们会看到check 函数怎么写直接决定了这道题能不能过。3. 二分答案的核心单调性分析3.1 单调性为什么可以用二分来解决二分答案能够成立必须有一个前提条件可行性随时间 t 的变化是单调的。简单说如果 t 时间内能干完那么 t1 时间内一定也能干完如果 t 时间内干不完那么更短的时间也一定干不完。这听起来像废话但它是整个二分的基石。为什么成立因为时间越多每件衣服自然风干掉的水分就越多留给烘干机处理的总量就越少烘干机的时间需求只会下降不会上升。所以“能干完”这个性质在时间轴上一定是从“否”变成“是”的而且一旦变成“是”后面一直是“是”。这个单调性非常重要因为只有满足单调性我们才敢用二分去收缩答案区间。如果可行性是非单调的比如时间长了反而干不完那二分就完全失效了。P1843 恰好是典型的单调场景所以二分答案在这里是安全的。3.2 二分什么答案区间怎么定接下来要确定二分的答案区间。下界很好理解最小时间不可能小于 0所以 l 0。上界要稍微想一下。一个绝对安全的上界是最湿的那件衣服完全靠自然风干能干的时长。为什么安全因为就算我们永远不使用烘干机只要时间足够长所有衣服终究会自然风干。所以答案不可能超过这个值。写成公式就是maxW / a考虑到整除保险起见再加 1。如果 a 为 0虽然题目一般不会这么贱但有些变种题会就需要额外判断这里按下不表。还有种写法是直接取一个很大的值比如 1e18作为上界。这种写法简单粗暴在某些二分模板里也够用。但个人建议还是用 maxW / a 1好处是答案区间更小二分的轮次略少最重要的是逻辑更清晰我们明确知道上界对应的是一个可行解。3.3 二分模板两种写法要选对二分模板有很多种我强烈建议初学者固定一种写法不要每次临时换。我习惯用的是左闭右开区间写法long long l 0, r maxW / a 1; // [l, r) while (l r) { long long mid (l r) / 2; if (check(mid)) r mid; else l mid 1; } cout l endl;这个模板的好处是语义清晰check(mid) 成立时答案在 [l, mid] 之间所以我们把右边界压到 mid不成立时答案在 [mid1, r] 之间所以我们把左边界提到 mid1。循环结束时l r就是答案。另一种常见写法是闭区间 [l, r]配合 l0, rmaxW/a1用 while(l r)mid(lr)/2check 成立则 rmid-1否则 lmid1。这在某些情况下也正确但对新手的思维负担略大容易搞混退出条件。我建议先用左闭右开这一个模板练熟了再谈变式。这里还要强调一点mid 的计算不要写成 (l r) / 2 以外的东西。虽然这题数据范围内 lr 不会溢出但你用 long long 保底之后这个表达式是绝对安全的。有些同学喜欢写 l (r - l) / 2 来防溢出也没问题纯属个人习惯。4. check 函数贪心验证是关键4.1 验证思路给你 t 分钟到底够不够二分答案的灵魂全在 check 函数里。check(t) 要回答的问题是如果只给我 t 分钟我能不能让所有衣服变干我们站在 t 分钟这个时间点往回看。每件衣服在这 t 分钟内即使不用烘干机也能自然风干掉 a·t 的水分。所以每件衣服“还需要额外处理的水分”就是long long remain w[i] - a * t;如果 remain 小于等于 0说明这件衣服靠着自然风干已经干了不需要烘干机。如果 remain 大于 0那这部分水分就必须由烘干机来去除。烘干机每单位时间能处理 b 的水分所以这件衣服需要占用烘干机的时间是long long need (remain b - 1) / b; // 向上取整把所有衣服的 need 累加起来得到总需求 sumNeed。如果 sumNeed t说明 t 分钟内烘干机的工作量装得下如果 sumNeed t说明就算烘干机满负荷工作也处理不完这么多额外水分。所以 check 函数的核心就是计算所有衣服需要的烘干机总时长然后和 t 比较。4.2 向上取整一个容易栽跟头的细节上面那个 need 的计算公式是这道题最容易出 bug 的地方。如果你写的是 remain / b那是向下取整。比如 remain 5b 2remain / b 2但实际上 2 个单位时间只能处理 4 的水分还剩 1 的水分没干所以需要 3 个单位时间。正确做法是向上取整。通用的写法是long long need (remain b - 1) / b;原理很简单remain 除以 b如果正好整除结果就是 remain / b如果不能整除remain b - 1 除以 b 的结果会比 remain / b 大 1恰好达到向上取整的效果。这个方法比调库函数 ceil 更高效也不会因为浮点精度问题出错。我见过不少同学在这里用(int)ceil(remain / (double)b)在小数据下没问题但一旦 remain 和 b 都是很大的整数浮点数精度误差就可能把答案差个 1导致判题 WA。切记整数取整一定用整数运算不要碰浮点。4.3 为什么贪心是对的给一个简短证明可能有同学会问把所有衣服需要的烘干机时间直接加起来比较不做任何调度安排这样真的够吗万一烘干机时间不够碎片化某些时间段安排不过来怎么办这里其实有一个很简单但深刻的贪心论证。对于固定时间 t每件衣服需要占用烘干机的总时长已经由公式确定了这些“任务”之间没有任何先后依赖关系也没有说烘干机必须在某个特定时段使用。那么所有任务的总时长之和不超过 t就一定能安排在 [0, t] 这个时间窗口内——把它们像拼积木一样首尾相连地排进去就行每件衣服用完烘干机后剩余时间照样可以自然风干。反过来如果总时长之和大于 t就算调度得再完美烘干机总工作量超载也不可能完成。所以“总需求 t”既是充分条件也是必要条件。这个贪心论证是 check 函数正确性的根基理解了这一点你在考场上有信心写错了也能自己排查。4.4 常见实现错误漏掉已经干透的衣服写 check 函数时最常见的错误就是没有先判断 remain 是否大于 0直接就把负值拿去算 need。比如一件衣服 w[i] 3a 2t 5那么 remain 3 - 10 -7。如果你不判断直接用 (-7 b - 1) / b在 C 里负数除法的结果是向零取整还是向负无穷取整不同版本可能有细微差异但总之会出现一个非预期的值污染总和。正确的写法一定是在累加前先判断if (remain 0) { sum (remain b - 1) / b; }还有一个隐藏问题如果 b 特别大而 remain 又很小need 计算结果可能是 0。0 表示这衣服需要烘干机的时间不足一个单位但题目中以单位时间为粒度这种情况其实应该是 1 个单位时间因为烘干机至少要开一下。不过由于我们最后比较的是 sumNeed 和 t而 need0 不会对总和造成贡献实际影响很小。更严谨的做法是把 need 至少计为 1但在 P1843 这种题里只要 remain 0公式(remain b - 1) / b算出的结果必然 1因为分子至少是 b所以不需要额外处理。5. 完整代码与逐行解读5.1 完整可提交的 C 代码我把核心代码写出来这个代码可以直接提交到 luogu P1843亲测 ACAccepted通过。#include bits/stdc.h using namespace std; const int MAXN 500005; int n; long long a, b; long long w[MAXN]; bool check(long long t) { long long sum 0; for (int i 0; i n; i) { long long remain w[i] - a * t; if (remain 0) { sum (remain b - 1) / b; if (sum t) return false; // 提前退出省时间 } } return sum t; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n a b; long long maxW 0; for (int i 0; i n; i) { cin w[i]; if (w[i] maxW) maxW w[i]; } long long l 0; long long r maxW / a 1; while (l r) { long long mid (l r) / 2; if (check(mid)) { r mid; } else { l mid 1; } } cout l \n; return 0; }这段代码整体不长但每部分都有讲究。下面拆开讲。5.2 关键代码行的解释先看 check 函数里的提前退出。我在 sum 累加后加了一行if (sum t) return false;这是个小优化。因为 sum 一旦超过 t后续不管有多少衣服结果必然是不成立提前返回可以省下很多次无效的取整计算。在 n 50 万且 t 很小时这个优化能让运行时间明显下降。再看主函数里的二分上界r maxW / a 1。加 1 是为了处理整除边界问题。比如 maxW 10a 3maxW / a 3但实际自然风干需要 4 个单位时间才能让含水量降到非正3 个时间单位只能去掉 9 的水分还剩 1。所以上界加 1 是安全且必要的。有同学可能问为什么不直接用r maxW或者r 1e18先说 r maxW这个上界可能小于真实答案比如 a 1maxW 10那真实答案可能是 10 甚至更大如果 b 也很小答案会超过 maxW而 maxW / a 1 已经考虑了速度是个紧且超的上界。至于 1e18虽然可行但会多几次二分没必要。5.3 数据范围与类型选择为什么必须用 long long这是一个我必须单独拿出来强调的点。P1843 的 n 最大是 5×10^5w[i] 和 a、b 都可能达到 10^9 级别。你在 check 函数里要算 w[i] - a * t其中 a * t 在 t 取到较大值时可能超过 10^18这已经远远超过 int 能表达的 2.1×10^9 了。我见过太多人用 int 写样例过了提交却 WA 或者 RE。问题就出在a * t爆 int变成负数或截断值导致后续判断全错。所以劝大家一句凡是涉及变量相乘、累加且数据范围比较大的题目别犹豫直接 long long。这不会带来性能问题反而能帮你省掉一个隐藏的致命 bug。甚至可以说我给这份代码里所有变量都开了 long long除了 n 用 int 足够就是要养成“常量级别分析”的习惯先看一眼数据范围再决定类型而不是等出错再回头改。6. 调试实录与问题排查6.1 样例过了但 WA优先检查二分边界做二分答案的题最揪心的就是“样例能过一提交就 WA”。如果你也遇到这个情况不要慌按优先级排查。第一个要查的就是二分边界。看看左边界是不是从 0 开始右边界是不是足够大如果 r 取小了比如你让 r maxW / b 1而 b 非常大时 r 会非常小可能正确答案根本不在区间里那就永远二分不到答案。第二个要查的是二分循环条件和收缩规则。左闭右开模板里check(mid) 成立时一定要 r mid而不是 r mid - 1。一旦写成 r mid - 1可能把正确答案跳过相反check(mid) 不成立时 l mid 1这个 1 不能省否则会死循环。第三个要查的是输出位置。二分结束后输出的是 l也就是 r而不是 mid 或者某个临时变量。mid 在循环结束后未必保存着正确答案直接输出 mid 是非常危险的。6.2 运行超时看看你的 check 函数有没有多余操作P1843 的 n 有 50 万check 函数每次 O(n)二分约 30 次总操作量是 1500 万级别完全在时限内。如果你超时了大概率是 check 函数里写了额外的高开销操作。比较常见的画蛇添足操作有几个在 check 内部对数组排序、每次调用 check 都重新初始化一个 vector、或者用 map / set 存储某种状态。这些都不需要。check 函数只需要一次 O(n) 遍历任何多余的数据结构都是在浪费宝贵的运行时间。还有一个小优化是提前退出我在前面提到过。如果 sum 已经大于 t立刻返回 false不要继续循环。这个优化在最坏情况下能把运行时间砍掉近一半属于“零成本”的优化建议大家养成习惯。6.3 答案总差 1大概率是整除向上取整的锅遇到“答案比标准答案小 1”的情况十有八九是向上取整写错了。比如你把 need 写成了remain / b 1这在 remain 恰好整除 b 时会比正确值大 1或者写成了remain / b则在不能整除时比正确值小 1。还有一个常见的隐藏问题(remain b - 1) / b这个公式只适用于 remain 和 b 都是正数的情况。如果 remain 是 0 或负数就不要进入这个分支。代码里先判断if (remain 0)再计算就是为了保证公式的使用前提。调试这类问题时我有个习惯造几组小数据手算一遍再跑程序对比。比如 n2w[5, 5]a1b2手算答案应该是 3。你可以把 check(3) 和 check(2) 都手动算一遍再跟程序输出对比很快就能定位是公式错了、边界错了还是整体思路错了。6.4 常见错误速查表错误现象可能原因解决办法样例都过不了把自然风干和烘干机理解成互斥回归题意烘干机是额外减少自然风干同时生效小数据对大数据 WAint 溢出所有相关变量改为 long long答案偏小向上取整写成了向下取整用 (remain b - 1) / b答案偏大 1整除时也额外加 1检查取整公式不要随意 1死循环二分收缩规则错误左闭右开成立 rmid不成立 lmid1超时check 内部有冗余操作只做一次 O(n) 遍历加提前退出某些测试点 RE数组开小了根据 n 的最大值开 MAXN留足余量7. 题目背后的算法套路从 P1843 到更多二分题7.1 什么样的题适合用二分答案P1843 不是孤例它代表了一类非常常见的题型求某个“可行性随时间或其他单调变量变化”的最值。判断一道题能不能用二分答案通常可以问自己三个问题问题目标是不是求“最小 xxx”或“最大 xxx”这个 xxx 的变化是否单调也就是说xx 越大可行性越强给定一个具体的 xxx我是否能在多项式时间内判断它是否可行如果三个答案都是“是”那这道题大概率就是二分答案。拿现实生活打个比方想象你在找一个“恰好能让自己不迟到的最晚出门时间”。出门时间越早越不容易迟到越晚越容易迟到这是单调的。你可以二分出门时间每天试验一次很快就能逼近最晚出门时刻。你不需要精确推演每一条路口的红绿灯只需要判断某次能不能到。7.2 同类题目对比换汤不换药二分答案的经典题目还有很多我列几个常见的方便大家横向对比。题目二分对象check 函数核心P1843 奶牛晒衣服最短时间烘干机总时长 时间P1873 砍树锯片最大高度砍到的木材总长度 需求P2678 跳石头最大最短跳跃距离需要移除的石头数 限制P1182 数列分段每段最大和的最小值在限制下能否分成不超过 m 段看出来了吧套路几乎一样。外层二分枚举答案内层用一个贪心或简单计算判断可行性。区别只在 check 的具体写法上。P1843 的 check 是靠求和比较P1873 的 check 是遍历树高累加P2678 的 check 是贪心数石头。你只要把 P1843 吃透再去做这几个题就会发现二分的骨架完全一致只需要替换不同的 check 实现。7.3 最小化最大值与最大化最小值再拔高一层。二分答案题还有一个常见的分类视角求“最小化最大值”和“最大化最小值”。P1843 属于“最小化最大值”类。我们要让“所有衣服干透所需的总时间”这个最大值尽可能小而 check 就是验证一个时间是否能让所有衣服都在这个时间之前干完。P1182 数列分段也是这一类我们要让“每一段的和中的最大值”最小。P2678 跳石头则属于“最大化最小值”类。我们要让“任意相邻石头间的最短距离”尽可能大同时保证移除的石头数不超过限制。这两种题目在二分时判断语义是反的求最小的最大值我们二分的区间左边界是“不行的”右边界是“行的”最终收缩到最小可行值求最大的最小值二分的左边界是“行的”右边界是“不行的”逻辑完全对称。刷题时建议把这两类分开整理不要混在一起。8. 个人经验与备考建议这道题我前前后后给好几个准备 GESP 五级的学生讲过每次讲到 check 函数里的向上取整都会有人踩坑。我自己第一遍写这题时也在二分边界上卡了很久后来养成了一个固定套路分享给大家。先说编码层面的习惯写二分答案题先写 check 函数再写二分框架。check 是这道题的灵魂先确保 check 在给定一个 t 时能正确判断可行性再去纠结二分边界。如果你 check 写错了二分框架再标准也没用。而且 check 函数是独立的你可以单独拿几个小数据验证它。再说一个做题心态上的建议GESP 五级的算法题通常不是让你发明新算法而是考察你能不能识别经典套路并正确实现。像二分答案、贪心、简单动态规划这些都是“书上有名、考场上常用”的东西。平时练题时要有意识地总结题型遇到“求最短/最小/最大 单调性明显”的组合就自动往二分答案上靠。练多了考场上看到题就能快速定位。最后说一个我反复提及但很多新手不当回事的问题long long。不是所有题都用得到但只要数据范围有超过 10^5 的迹象我建议直接 long long 起步。它不会让代码变慢也不会让你的代码变丑但它能在一夜之间救你于 WA 的苦海之中。比赛时根本没时间慢慢排查溢出问题最好的办法是从源头堵死。这道题的延伸价值也很高。如果你能把 P1843 独立写出来我建议马上去刷 P1873 砍树再把 P2678 跳石头也做了。这三道题连起来刷一遍二分答案这个知识点基本上就形成了肌肉记忆。以后再遇到任何求最值的题你都不会再第一时间陷入模拟的死胡同而是条件反射地开始思考“这题能不能二分”。这个思维转变才是你做这道题最大的收获。