class Solution {
public:
long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
}
};
3296. 移山所需的最少秒数
给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
x，需要花费 workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x 秒。例如：
workerTimes[i] 秒。workerTimes[i] + workerTimes[i] * 2 秒，依此类推。返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
示例 1：
输入： mountainHeight = 4, workerTimes = [2,1,1]
输出： 3
解释：
将山的高度降低到 0 的一种方式是：
workerTimes[0] = 2 秒。workerTimes[1] + workerTimes[1] * 2 = 3 秒。workerTimes[2] = 1 秒。因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。
示例 2：
输入： mountainHeight = 10, workerTimes = [3,2,2,4]
输出： 12
解释：
workerTimes[0] + workerTimes[0] * 2 = 9 秒。workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 秒。workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 秒。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 <= 1051 <= workerTimes.length <= 1041 <= workerTimes[i] <= 106原站题解
java 解法, 执行用时: 212 ms, 内存消耗: 44.9 MB, 提交时间: 2024-09-23 11:38:51
class Solution {
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
for (int t : workerTimes) {
pq.offer(new long[]{t, t, t});
}
long ans = 0;
while (mountainHeight-- > 0) {
// 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
long[] w = pq.poll();
long nxt = w[0], delta = w[1], base = w[2];
ans = nxt; // 最后一个出堆的 nxt 即为答案
pq.offer(new long[]{nxt + delta + base, delta + base, base});
}
return ans;
}
}
golang 解法, 执行用时: 140 ms, 内存消耗: 6.2 MB, 提交时间: 2024-09-23 11:38:31
func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
h := make(hp, len(workerTimes))
for i, t := range workerTimes {
h[i] = worker{t, t, t}
}
heap.Init(&h)
ans := 0
for ; mountainHeight > 0; mountainHeight-- {
ans = h[0].nxt // 最后一个出堆的 nxt 即为答案
h[0].delta += h[0].base
h[0].nxt += h[0].delta
heap.Fix(&h, 0)
}
return int64(ans)
}
// 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
type worker struct{ nxt, delta, base int }
type hp []worker
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].nxt < h[j].nxt }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (hp) Push(any) {}
func (hp) Pop() (_ any) { return }
golang 解法, 执行用时: 18 ms, 内存消耗: 5.6 MB, 提交时间: 2024-09-23 11:38:16
func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
maxT := slices.Max(workerTimes)
h := (mountainHeight-1)/len(workerTimes) + 1
ans := 1 + sort.Search(maxT*h*(h+1)/2, func(m int) bool {
m++
leftH := mountainHeight
for _, t := range workerTimes {
leftH -= int((math.Sqrt(float64(m/t*8+1)) - 1) / 2)
if leftH <= 0 {
return true
}
}
return false
})
return int64(ans)
}
python3 解法, 执行用时: 647 ms, 内存消耗: 18.5 MB, 提交时间: 2024-09-23 11:37:58
class Solution:
def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
h = [(t, t, t) for t in workerTimes]
heapify(h)
for _ in range(mountainHeight):
# 工作后总用时，当前工作（山高度降低 1）用时，workerTimes[i]
nxt, delta, base = h[0]
heapreplace(h, (nxt + delta + base, delta + base, base))
return nxt # 最后一个出堆的 nxt 即为答案
# 二分
def minNumberOfSeconds2(self, mountainHeight: int, workerTimes: List[int]) -> int:
def check(m: int) -> bool:
left_h = mountainHeight
for t in workerTimes:
left_h -= int((sqrt(m // t * 8 + 1) - 1) / 2)
if left_h <= 0:
return True
return False
max_t = max(workerTimes)
h = (mountainHeight - 1) // len(workerTimes) + 1
return bisect_left(range(max_t * h * (h + 1) // 2), True, 1, key=check)
# bisect
def minNumberOfSeconds3(self, mountainHeight: int, workerTimes: List[int]) -> int:
f = lambda m: sum(int((sqrt(m // t * 8 + 1) - 1) / 2) for t in workerTimes)
max_t = max(workerTimes)
h = (mountainHeight - 1) // len(workerTimes) + 1
return bisect_left(range(max_t * h * (h + 1) // 2), mountainHeight, 1, key=f)