企业官网建设流程全解析

最近刷 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 时间内能干完，那么 t+1 时间内一定也能干完；如果 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；不成立时，答案在 [mid+1, r] 之间，所以我们把左边界提到 mid+1。循环结束时，l == r，就是答案。

另一种常见写法是闭区间 [l, r]，配合 l=0, r=maxW/a+1，用 while(l <= r)，mid=(l+r)/2，check 成立则 r=mid-1，否则 l=mid+1。这在某些情况下也正确，但对新手的思维负担略大，容易搞混退出条件。我建议先用左闭右开这一个模板，练熟了再谈变式。

这里还要强调一点：mid 的计算不要写成 (l + r) / 2 以外的东西。虽然这题数据范围内 l+r 不会溢出，但你用 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 = 5，b = 2，remain / 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] = 3，a = 2，t = 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，而 need=0 不会对总和造成贡献，实际影响很小。更严谨的做法是把 need 至少计为 1，但在 P1843 这种题里，只要 remain > 0，公式(remain + b - 1) / b算出的结果必然 >= 1，因为分子至少是 b，所以不需要额外处理。

5. 完整代码与逐行解读

5.1 完整可提交的 C++ 代码

我把核心代码写出来，这个代码可以直接提交到 luogu P1843，亲测 AC（Accepted，通过）。

#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 = 10，a = 3，maxW / a = 3，但实际自然风干需要 4 个单位时间才能让含水量降到非正（3 个时间单位只能去掉 9 的水分，还剩 1）。所以上界加 1 是安全且必要的。

有同学可能问：为什么不直接用r = maxW或者r = 1e18？先说 r = maxW，这个上界可能小于真实答案，比如 a = 1，maxW = 10，那真实答案可能是 10 甚至更大，如果 b 也很小，答案会超过 maxW；而 maxW / a + 1 已经考虑了速度，是个紧且超的上界。至于 1e18，虽然可行，但会多几次二分，没必要。

5.3 数据范围与类型选择：为什么必须用 long long

这是一个我必须单独拿出来强调的点。P1843 的 n 最大是 5×10^5，w[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)再计算，就是为了保证公式的使用前提。

调试这类问题时，我有个习惯：造几组小数据，手算一遍，再跑程序对比。比如 n=2，w=[5, 5]，a=1，b=2，手算答案应该是 3。你可以把 check(3) 和 check(2) 都手动算一遍，再跟程序输出对比，很快就能定位是公式错了、边界错了还是整体思路错了。

6.4 常见错误速查表

7. 题目背后的算法套路：从 P1843 到更多二分题

7.1 什么样的题适合用二分答案

P1843 不是孤例，它代表了一类非常常见的题型：求某个“可行性随时间（或其他单调变量）变化”的最值。判断一道题能不能用二分答案，通常可以问自己三个问题：

• 问题目标是不是求“最小 xxx”或“最大 xxx”？
• 这个 xxx 的变化是否单调？也就是说，xx 越大，可行性越强？
• 给定一个具体的 xxx，我是否能在多项式时间内判断它是否可行？

如果三个答案都是“是”，那这道题大概率就是二分答案。

拿现实生活打个比方：想象你在找一个“恰好能让自己不迟到的最晚出门时间”。出门时间越早越不容易迟到，越晚越容易迟到，这是单调的。你可以二分出门时间，每天试验一次，很快就能逼近最晚出门时刻。你不需要精确推演每一条路口的红绿灯，只需要判断某次能不能到。

7.2 同类题目对比：换汤不换药

二分答案的经典题目还有很多，我列几个常见的，方便大家横向对比。

看出来了吧，套路几乎一样。外层二分枚举答案，内层用一个贪心或简单计算判断可行性。区别只在 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 跳石头也做了。这三道题连起来刷一遍，二分答案这个知识点基本上就形成了肌肉记忆。以后再遇到任何求最值的题，你都不会再第一时间陷入模拟的死胡同，而是条件反射地开始思考“这题能不能二分”。这个思维转变，才是你做这道题最大的收获。