当前位置：首页 > news >正文

LeetCode 3296.移山所需的最少秒数

news 2026/6/30 2:07:05

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

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

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

山的高度降低 1，需要 workerTimes[i] 秒。
山的高度降低 2，需要 workerTimes[i] * 2 秒。
…
山的高度降低 x，需要 workerTimes[i] * x 秒。
工人 i 所花费的总时间是所有 x 单位所需时间的总和。由于所有工人同时操作，所需的总时间是任何工人花费的最大时间。

返回一个整数，表示工人们使山的高度降低到 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^55
1 <= workerTimes.length <= 104^44
1 <= workerTimes[i] <= 106^66

直接模拟，循环mountainHeight次，每次循环中一个工人降低1的高度，取工作总时间最短的那个工人，这可以用小顶堆来实现：

classSolution{public:longlongminNumberOfSeconds(intmountainHeight,vector<int>&workerTimes){vector<tuple<longlong,longlong,int>>h(workerTimes.size());for(inti=0;i<workerTimes.size();++i){h[i]={workerTimes[i],workerTimes[i],workerTimes[i]};}make_heap(h.begin(),h.end(),greater());longlongans=0;while(mountainHeight>0){// 已工作的总时间，当前使高度降低1所需时间，初始使高度降低1所需时间auto[total,need,base]=h[0];// 每次更新答案为已工作的总时间ans=total;pop_heap(h.begin(),h.end(),greater());h.back()={total+need+base,need+base,base};push_heap(h.begin(),h.end(),greater());--mountainHeight;}returnans;}};