3296.移山所需的最少秒数：优先队列

【LetMeFly】3296.移山所需的最少秒数：优先队列

力扣题目链接：https://leetcode.cn/problems/minimum-number-of-seconds-to-make-mountain-height-zero/

给你一个整数 mountainHeight 表示山的高度。

同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。

工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :

• 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：

  <ul>
  	<li>山的高度降低 1，需要 <code>workerTimes[i]</code> 秒。</li>
  	<li>山的高度降低 2，需要 <code>workerTimes[i] + workerTimes[i] * 2</code> 秒，依此类推。</li>
  </ul>
  </li>
  

返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。

 

示例 1：

输入： mountainHeight = 4, workerTimes = [2,1,1]

输出： 3

解释：

将山的高度降低到 0 的一种方式是：

• 工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
• 工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
• 工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。

因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。

示例 2：

输入： mountainHeight = 10, workerTimes = [3,2,2,4]

输出： 12

解释：

• 工人 0 将高度降低 2，花费 workerTimes[0] + workerTimes[0] * 2 = 9 秒。
• 工人 1 将高度降低 3，花费 workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。
• 工人 2 将高度降低 3，花费 workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。
• 工人 3 将高度降低 2，花费 workerTimes[3] + workerTimes[3] * 2 = 12 秒。

所需的最少时间为 max(9, 12, 12, 12) = 12 秒。

示例 3：

输入： mountainHeight = 5, workerTimes = [1]

输出： 15

解释：

这个示例中只有一个工人，所以答案是 workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15 秒。

 

提示：

• 1 <= mountainHeight <= 105
• 1 <= workerTimes.length <= 104
• 1 <= workerTimes[i] <= 106

解题方法：优先队列

使用一个优先队列，每次选完工最早的工人降低1个山高。工人完工后可以再次进入队列，只不过再次进入队列后的下次工作耗时更久而已。

具体来说，优先队列中存放每个工人的(完工时间, 共计降低高度, baseTime)，共计降低高度和baseTime都是为了计算完工时间。

• 时间复杂度$O(height\times \log n)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-13 22:57:56
 */
typedef long long ll;
class Solution {
public:
    ll minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        priority_queue<tuple<ll, ll, int>, vector<tuple<ll, ll, int>>, greater<>> pq;
        for (int t : workerTimes) {
            pq.push({t, 1, t});
        }
        ll ans = 0;
        while (mountainHeight--) {
            auto[now, times, once] = pq.top();
            pq.pop();
            ans = now;
            pq.push({now + ++times * once, times, once});
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源