说个可能反直觉的事LeetCode 3296 这道题第一眼看到“移山所需的最少秒数”大多数人会本能地往二分答案上冲因为“最少时间”在 LeetCode 里几乎已经被二分搜索焊死了。但真正把这道题吃透之后你会发现优先队列最小堆反而更贴近题目本质它直接把每个工人看成一条“持续产出完成事件”的时间轴然后用多路归并的方式一路取到第mountainHeight个事件。这个思路既能解释最优解为什么长这样也能顺便把“为什么二分也能过”背后的道理讲明白。这篇文章我不打算只贴一段能 AC 的代码我会从题意中的“疲劳公式”开始拆把优先队列里的每个字段为什么这么设计、每次 pop 之后为什么要 push 回同一个工人、以及workerTimes[i] * k(k1)/2这个公式到底怎么来的都过一遍。最后再把二分答案的 check 函数和堆模拟放在一起对比适合哪些数据范围、各自坑在哪一次说清楚。1. 先把题目的“疲劳公式”捋清楚1.1 题意还原题目里的工人不是“每秒移 1 单位”的匀速机器。第i个工人有基础耗时workerTimes[i]但是当他完成第1次移山后后面会越来越慢。准确说第1次移山耗时workerTimes[i]第2次移山耗时2 * workerTimes[i]第3次移山耗时3 * workerTimes[i]第k次移山耗时k * workerTimes[i]。所以一个工人如果连续干了k次他完成这k次的总时间就是workerTimes[i] * (1 2 ... k) workerTimes[i] * k * (k 1) / 2这就是这道题最核心的公式。很多题解直接扔出这个式子上二分但没有解释为什么是“三角数”。你可以把每次移山想成越来越重的土方第一次只要挖表面的松土第二次要挖更深更硬的土第三次更费劲于是用时线性增长。这种模型在真实体力劳动里很常见也决定了我们不能简单地用h / n去平均分配。我举个例子。假设workerTimes [2, 3]山高h 4。工人 A 完成第 1 次是第 2 秒第 2 次是第 6 秒第 3 次是第 12 秒工人 B 完成第 1 次是第 3 秒第 2 次是第 9 秒第 3 次是第 18 秒。如果你让 A 干 2 次、B 干 2 次那么 A 最后一次在第 6 秒完成B 最后一次在第 9 秒完成总耗时 9 秒。如果你让 A 干 3 次、B 干 1 次总耗时是max(12, 3) 12秒。显然 9 秒更优。这个例子小到可以手算但一旦h变大靠枚举分配次数是完全不现实的。1.2 完成事件的视角每个工人从第0秒开始就在干活他会在固定的时间点“产出”一次移山完成事件。工人i的第k次完成时间可以写成T_i(k) workerTimes[i] * (1 2 ... k)注意这是一个严格递增的序列。于是整个问题可以换成另一种说法有n条递增序列每条序列的第k项是T_i(k)。我们想要选出h个完成事件让最后一个事件发生的时间尽可能早。因为每个工人的序列都是“先发生小的再发生大的”如果你想让全局第h个单位最早完成那就应该取所有完成事件里最小的h个。第h小的那个完成时间就是答案。这个视角非常关键。它把调度问题转化成了一个“多路归并求前h小”的问题而多路归并正是优先队列最擅长的场景。2. 优先队列建模把工人当成持续产出的流2.1 多路归并的直觉你可以把每个工人想象成一条流水线流水线每隔越来越长的时间吐出一个“已完成单位”。所有流水线同时开动我们需要关注的是全局第h个产出发生在什么时刻。这里不需要真的去“分配”任务因为工人之间互不影响且每个工人都应该从第0秒开始工作。如果某个工人在中途休息那他后面的完成时间只会被推迟不可能让整体更早完成。一开始所有工人都在做自己的第1次移山所以第1个完成事件会出现得比较早。当某个工人完成一次后他立刻开始下一次移山下一次耗时会增加。这个过程天然形成一种动态的事件流。为了在任意时刻拿到当前最早发生的事件我们只需要一个按“事件发生时间”排序的最小堆。这跟你合并k个有序链表时用的堆一模一样。每个工人的完成时间序列是有序的堆里存的是每条链表的“当前节点”每次弹出最小的节点然后把该工人序列的下一个节点入堆。循环h次最后一次弹出的时间就是答案。2.2 堆里存什么字段我见过不少人一开始把堆里只存一个“下次完成时间”结果更新的时候傻眼了因为下一个完成时间不仅要加workerTimes[i]还要加入“第几次”的信息。核心原因在第 1 节每次移山的耗时不是常量而是随次数线性增长。所以堆里的每个节点至少需要三个信息t这个工人即将完成当前这次移山的时刻k他当前即将完成的是第k次移山id工人编号用来取workerTimes[id]。初始状态很简单每个工人都从第0秒开始干第1次移山所以入堆(workerTimes[i], 1, i)。当从堆里弹出一个节点时代表这个工人在时刻t又完成了一单位高度。我们把这个t记下来如果这是第h次弹出那答案就是它。接下来要计算这个工人的下一次完成时间。假设他刚刚完成的是第k次下一次是第k 1次那么下一次移山本身耗时是(k 1) * workerTimes[id]。由于他是在时刻t开始下一次移山的所以下一次完成时间就是t (k 1) * workerTimes[id]然后把(t (k 1) * workerTimes[id], k 1, id)重新入堆。这里最容易错的地方是不要在弹出时用t (k) * workerTimes[id]。因为下一次移山的耗时单位编号是k 1不是k。比如workerTimes [2]工人完成第 1 次在第 2 秒第 2 次耗时2 * 2 4秒所以第 2 次完成时间是2 4 6对应的是k 1 2。如果用k就会算出2 2 4那就错了。2.3 为什么取前 h 小就是全局最优这个问题很多人跳过但必须想清楚。我们构造的调度方案是“每个工人从第 0 秒开始连续工作直到全局完成 h 个单位”。假设堆每次弹出的都是全局最小的完成事件那么取前h个事件后对每个工人来说被取到的完成事件一定是一个前缀。为什么因为工人的完成时间序列是严格递增的。如果他的第k次完成事件被取到了意味着这个时间排进了前h小那么他前面的1..k-1次完成事件肯定更早也一定会被取到。所以每个工人最终被分配的次数cnt[i]满足sum(cnt[i]) h并且这个方案的最大完成时间就是第h个事件的时刻。反过来任何可行方案在T秒内完成h个单位都必须满足每个工人只能完成前面若干次因此h不会超过“所有完成时间不超过 T 的事件总数”。这说明最优解的下界就是第h小的完成事件时刻。堆模拟取到的恰好达到这个下界所以它是最优的。用大白话总结所有人的所有“可能完成时刻”摆在一起最优答案就是第h小的那个。优先队列做的事情只是把这h个最小的时刻按顺序逐个找出来不需要把整个完成时刻表提前算好。3. 手把手写代码C 优先队列版3.1 完整代码直接上 C 代码long long是必须的因为三角数增长很快int会在山高稍微大一点的时候溢出。using ll long long; struct Node { ll t; // 这个工人完成“当前第 k 次移山”的时刻 ll k; // 当前这是第 k 次移山 int id; // 工人编号 Node(ll _t, ll _k, int _id) : t(_t), k(_k), id(_id) {} // 小顶堆t 小的优先 bool operator(const Node other) const { return t other.t; } }; class Solution { public: long long minimumSeconds(vectorint workerTimes, int mountainHeight) { priority_queueNode pq; int n workerTimes.size(); // 所有工人从第 0 秒开始先干第 1 次移山 for (int i 0; i n; i) { pq.emplace(workerTimes[i], 1, i); } ll ans 0; for (int h 0; h mountainHeight; h) { Node cur pq.top(); pq.pop(); // 第 h 个单位完成于 cur.t ans cur.t; // 这个工人下一次要完成第 cur.k 1 次移山 ll nextK cur.k 1; // 下一次完成时间 当前完成时间 (下一次移山的耗时) // cur.t (cur.k 1) * workerTimes[cur.id] pq.emplace(cur.t nextK * workerTimes[cur.id], nextK, cur.id); } return ans; } };注意循环次数是mountainHeight不是workerTimes.size()。我见过有人把两个数搞反直接死循环或者答案明显偏小。每次循环对应一个单位的高度被移走所以循环多少次完全由山高决定。3.2 一个可以手算的样例还是用workerTimes [2, 3]mountainHeight 6来模拟一遍。初始堆工人当前第 k 次完成时刻 tA12B13依次弹出第 1 次弹出 At 2。之后 A 的第 2 次完成时刻是2 2*2 6入堆。第 2 次弹出 Bt 3。之后 B 的第 2 次完成时刻是3 2*3 9入堆。第 3 次弹出 A第 2 次移山t 6。之后 A 的第 3 次完成时刻是6 3*2 12入堆。第 4 次弹出 B第 2 次移山t 9。之后 B 的第 3 次完成时刻是9 3*3 18入堆。第 5 次弹出 A第 3 次移山t 12。之后 A 的第 4 次完成时刻是12 4*2 20入堆。第 6 次弹出 A第 4 次移山t 14?等等这里重新算A 第 3 次完成时刻是 12第 4 次耗时4*28所以第 4 次完成是12820不是 14。堆里当前有 B 的第 3 次完成时刻 18以及 A 的第 4 次 20所以第 6 次弹出 B 的 18答案是 18。之前我们算过h4时答案是 9h6时答案是 18。验证一下是否合理如果 A 分配 4 次A 最后完成在 20如果 A 分配 3 次、B 分配 3 次最大时间max(12, 18) 18更优。堆模拟给出的正是 18说明它确实在自动平衡。这个例子告诉我们一个直观规律堆不是简单地让快的工人一直干而是在“快的工人下一次完成时间”和“慢的工人下一次完成时间”之间做比较。刚结束那次模拟里A 完成第 3 次后下一次要等 8 秒B 完成第 2 次后下一次要等 9 秒两者接近所以会交替干活。堆的价值就体现在这种动态抉择上。3.3 复杂度分析优先队列里最多有n个节点每次 pop 和 push 都是O(log n)。总共要 poph次每次都会 push 一次所以时间复杂度是O(h log n)空间复杂度是O(n)。这个复杂度在n很大、h相对小时非常香。比如n 10^5h 10^5堆内 log 只有 17 左右跑起来很轻松。但如果h高达10^9堆模拟就要循环十亿次肯定不行。那种场景下二分答案才是正解。4. 二分答案另一种标准姿势4.1 给定 T每个工人能完成多少次二分答案的思路是我们不知道最少需要多少秒但可以猜一个答案T然后检查“在 T 秒内能不能移完 h 个单位”。如果能就缩小T如果不能就放大T。这需要写一个check(T)函数。对于工人i他在T秒内能完成k次需要满足workerTimes[i] * k * (k 1) / 2 T令x T / workerTimes[i]整除即可条件变成k * (k 1) / 2 x解这个一元二次不等式得到最大的kk floor((sqrt(1 8 * x) - 1) / 2)然后把所有工人的k加起来看是否大于等于mountainHeight。这里用整除是没问题的因为workerTimes[i] * k(k1)/2 T等价于k(k1)/2 floor(T / workerTimes[i])。比如T 7workerTimes [2]x 3最大k是满足12...3的 2因为123第 3 次要 6 秒总 12 秒超过 7。用公式也能算出来。写出来的 check 长这样bool check(long long T, vectorint workerTimes, int mountainHeight) { long long total 0; for (int w : workerTimes) { long long x T / w; long long k (sqrtl(1.0L 8.0L * x) - 1.0L) / 2.0L; total k; if (total mountainHeight) return true; } return false; }然后二分T的范围。下界可以是0上界要足够大。最保守的做法是取1e18但要注意sqrtl内部计算8.0L * x时如果x接近1e178*x也到不了long long的极限9.22e18所以取1e18刚好还能扛住。更稳的办法是用__int128一步步算不过竞赛环境里多数时候long double配合sqrtl已经够用。4.2 二分和堆到底选谁如果你把这两种解法放在一起会发现它们的 check 目标和证明其实是同一个东西堆模拟找的是第h小的完成事件二分 check 统计的是“在 T 秒内有多少个完成事件小于等于 T”。前者是一个一个数后者是批量数。所以当h比较小比如10^5以内优先队列模拟直观、不易写错而且不需要考虑浮点精度问题当h非常大比如10^9堆模拟循环次数太多只能靠二分批量计算。有一道经典题和这个 check 思路几乎是一对就是 LeetCode 875“爱吃香蕉的狒狒”。那道题里check(k)是sum ceil(pile / k) h判断速度够不够这道题的check(T)是sum floor((sqrt(18*T/w)-1)/2) h判断时间够不够。两道题一起刷你对“答案单调性”和“取整边界”的理解会深很多。二分代码里我最想提醒的一点不要拿sqrt去算要用sqrtl并且常数要写成8.0L。否则当x很大时普通sqrt(double)的精度损失可能导致k差 1最后 check 结果错误。这种错很难查因为小样例全对大样例偶尔挂。5. 常见问题与避坑实录5.1 用 int 存时间溢出是迟早的事假设一个工人workerTimes[i] 10^5连续做 1000 次总时间已经是10^5 * 1000 * 1001 / 2 ≈ 5 * 10^10早就超过int范围。更别说 LeetCode 的边界还会给到更大的mountainHeight。所以t、k、ans以及二分里的x全部用long long。如果你在本地编译器上跑小数据没问题一提交就WA先去看类型。5.2 初始化时不要漏掉任何工人有些朋友会想山高只有 5但工人有 100 个难道所有工人都要入堆吗对全部都要入堆。虽然慢工人可能在前 5 次事件里永远出不来但你不把它放进去程序逻辑上就漏掉了“有可能某个慢工人在某时刻完成得更早”的情况。举个极端例子workerTimes [100, 101]h 1。两个工人第 1 次完成时间分别是 100 和 101答案显然是 100。如果你初始化时只放前h个工人并且恰好漏掉了快的答案就会错。所以初始化必须遍历所有工人把(workerTimes[i], 1, i)全部入堆。5.3 相等时间怎么处理优先队列会遇到两个节点t相同的情况比如两个工人同时完成当前单位。此时 pop 哪一个都不会影响答案因为第h个事件发生的时间都是同一个t。但有一个隐藏问题如果你在自定义比较器里只比较t堆结构没问题如果比较器里顺便比较id或者k也不会改变答案顶多是调度顺序不同。真正该注意的是比较器必须满足严格弱序不要在t相等时返回false又同时要求operator两边对称否则在某些编译器下会出奇怪行为。最简单的写法就是直接return t other.t;。5.4 二分上界别拍脑袋二分答案的上界如果写小了可能直接导致正确答案被排除。一个安全的hi可以这样算选最慢的工人maxWorkerTimes假设所有工作都由这个最慢的工人干他需要完成h次总时间是maxWorkerTimes * h * (h 1) / 2如果h是10^9这个值会到5e22超过long long。这时你可以把题目给的约束再翻出来看LeetCode 3296 的mountainHeight并没有夸张到那个程度所以long long加1e18的上界通常可行。但如果你在自定义数据范围玩建议用__int128做二分或者把 check 里的加法提前短路避免溢出。5.5 优先队列版能不能改成“排序数组”每次 pop 之后 push 回同一个工人本质上是在维护n个有序序列。如果你不想用堆也可以把所有工人的前h次完成时间全部暴力算出来排序后取第h个。但那样复杂度是O(nh log(nh))而且当n 10^5、h 10^5时一共要算10^10个事件内存和时间全部爆炸。优先队列每次只迭代一个事件同时保持每个工人的“下一个事件”待命这才是它快的原因。5.6 和“爱吃香蕉的狒狒”对比时容易踩的坑LeetCode 875 的h是“小时数”是二分对象而 3296 的mountainHeight是“工作量”不是时间。所以在 875 里 check 是每堆香蕉除以速度之后向上取整而 3296 的 check 是每个工人能完成多少单位向下取整。向上取整和向下取整用错答案会差很多。我建议把两条公式并排背下来875sum((pile speed - 1) / speed) h3296sum(floor((sqrt(1 8*T/w) - 1) / 2)) mountainHeight一个是判断“能不能在 h 小时内吃完”一个是判断“能不能在 T 秒内移完”方向相反很容易混。5.7 一个提升调试效率的小技巧如果你担心堆模拟写错可以先写一个暴力版本把每个工人的前h个完成时间全部生成到一个数组里排序后输出第h个值。用这个暴力版跟优先队列版对拍随机生成n和workerTimes跑几百组小数据。这个对拍不仅能验证主算法还能帮你确认“第 h 小的完成事件”这个模型是不是正确理解了题目。我每次遇到跟多路归并有关的问题都会先写暴力排序版因为它的正确性一目了然再拿它当标程去验堆写法省下大量手算时间。6. 一点个人体会这道题最让我意外的地方是“优先队列”和“二分答案”两个看起来完全不同的解法最后居然收敛到同一个数学事实答案就是所有完成事件中第h小的那个。堆是一个一个取二分是批量判断“小于等于 T 的事件总数够不够 h”。两者没有谁取代谁只是在不同数据规模下的表达方式。我个人在实际做这类题时会先在草稿纸上写出每个工人的完成时间序列看看是不是递增的能不能用多路归并然后再看数据范围决定用堆还是用二分。这个方法帮我避开过很多“一道题拿到手就只会套模板”的坑。LeetCode 3296 属于那种“公式看着吓人拆开之后全是套路”的题只要你把疲劳公式和堆里的k字段想清楚代码反而比普通二分答案题更不容易出错。