2025-04-25：移山所需的最少秒数。用go语言，给定一个整数 mountainHeight，代表一座山的高度。还有一个整|复杂度|整数|最大值|移山|算法

2025-04-25：移山所需的最少秒数。用go语言，给定一个整数 mountainHeight，代表一座山的高度。

还有一个整数数组 workerTimes，其中每个元素表示对应工人完成单位高度降低所需的时间（单位为秒）。

工人必须同时开始工作以降低山的高度。对于第 i 个工人，如果他降低了高度为 x，那么他所花费的时间是：

workerTimes[i] * (1 + 2 + ... + x) = workerTimes[i] * (x * (x + 1) / 2)

举例：

1.降低高度为 1，需要花费 workerTimes[i] 秒；

2.降低高度为 2，需要花费 workerTimes[i] * (1 + 2) 秒；

3.以此类推。

任务是求出所有工人一起合作，把山降到高度 0，所需的最小时间（秒数）。

也就是说，要合理分配工人降低的高度，使得他们各自的工作时间最大值最小，求出这个最小的最大工作时间。

1 <= mountainHeight <= 100000。

1 <= workerTimes.length <= 10000。

1 <= workerTimes[i] <= 1000000。

输入： 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 秒。

题目来自leetcode3296。

下面是详细的分步骤过程： 1. 理解问题和关键关系

• 每个工人 i 降低高度 x，需要时间：
workerTimes[i] × (1 + 2 + ... + x) = workerTimes[i] × x × (x + 1) / 2
• 所有工人同时开始工作，每个工人的工作时间可能不同。最终完成时间是所有工人工作的最大值。
• 目标是找到最小的时间T，在时间T内，所有工人合起来能至少降低mountainHeight的高度。

2. 将问题转换成判定问题

• 给定某个时间T，判定是否存在一个分配方案使得所有工人在 ≤T的时间内，总计降低高度至少mountainHeight。
• 对于工人 i，在时间限制T下，能降低的最大高度是多少？根据时间公式：
时间 = workerTimes[i] × x × (x + 1) / 2 ≤ T
解这个不等式求x：

1. 令M = T / workerTimes[i]
2. 则：x² + x - 2M ≤ 0
3. 解这个二次不等式，最大整数x为：
x = floor((√(1 + 8M) - 1) / 2)

3. 二分搜索的思路

• 最少时间的下界是 1 秒（至少需要1秒才能开始工作）。
• 上界是一个较大的时间，比如某个工人单独完成全部工作所需最大时间的保守估计。
• 用二分搜索在时间范围里寻找最小的时间midTime，根据步骤2对每个工人计算其最大降低高度，如果所有工人的降低高度之和 ≥mountainHeight，说明可以在该时间或更短时间完成。
• 如果不能完成，则需要增加时间；如果能完成，则尝试降低时间。

4. 具体步骤描述

步骤 1：初始化二分查找范围

• 计算最大工时：
找出 workerTimes 中的最大工作时间 maxT。
• 计算最坏情况下某工人单独降低所有高度需要的时间上限：假设每个工人分担平均高度h = (mountainHeight - 1) / len(workerTimes) + 1，
那么最大时间上界大约是：
maxT * h * (h + 1) / 2

步骤 2：进行二分搜索

• 利用sort.Search或经典二分搜索，在区间[1, maxTime]之间尝试时间m。

步骤 3：判断函数

• 对于给定时间m，计算每个工人在m时间下最大能降低高度：
根据公式：x = floor((√(1 + 8 * (m / workerTimes[i])) - 1) / 2)
• 累加所有工人的最大降低高度，得到总降低量totalLoweredHeight。
• 如果totalLoweredHeight >= mountainHeight，函数返回true表示时间m足够。
• 否则返回false。

步骤 4：根据判断结果调整搜索区间

• 如果时间m足够，尝试缩小区间向左搜索更小时间。
• 否则向右搜索更大时间。

步骤 5：最终返回最小满足条件的时间

• 二分搜索结束时返回找到的最小时间。

总体时间复杂度分析

• 二分搜索的次数是O(log(maxTime))，其中maxTime是最大时间界限，大致与山高度 * 最大工作时间成正比（但常数相对较大）。
• 每次二分判断函数中需要遍历所有n个工人，计算每个人最大降低高度，复杂度是O(n)。
• 因此总时间复杂度为O(n log maxTime)。

其中：

•n是工人数，最大 10000，
•maxTime最大可能很大，因为workerTimes[i]最大可达 10^6，mountainHeight最大 10^5，但log操作使得其可接受。

空间复杂度分析

• 除了存储输入的 workerTimes 和常量空间外，没有使用额外占用多倍大小的空间。
• 主要使用O(n)空间存储 workerTimes 和少量临时变量。
• 因此额外空间复杂度是O(n)。

总结

步骤

描述

问题转为判定是否给定时间内可完成任务

给定时间T，计算每个工人最大降低高度求和是否≥山高

二次方程求每个工人在时间限制下最大可降低高度

利用公式x = floor((√(1+8M)-1)/2)，其中M = T / workerTimes[i]

二分搜索时间区间寻找最优时间

利用二分法从时间区间中定位最小满足要求的时间

每次判定遍历工人计算高度

时间复杂度O(n)

总时间复杂度

O(n log(maxTime))

总空间复杂度

O(n)

这样就实现了高效求解工人同时完成降山任务的最短时间。

Go完整代码如下：

package main import (     "fmt"     "math"     "slices"     "sort" ) 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-1, 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 {                 returntrue             }         }         returnfalse     })     returnint64(ans) } func main() {     mountainHeight := 4     workerTimes := []int{2, 1, 1}     result := minNumberOfSeconds(mountainHeight, workerTimes)     fmt.Println(result) }

Python完整代码如下：

# -*-coding:utf-8-*- import math defmin_number_of_seconds(mountain_height: int, worker_times: list[int]) -> int:     max_t = max(worker_times)     h = (mountain_height - 1) // len(worker_times) + 1     defcan_finish(m: int) -> bool:         left_h = mountain_height         for t in worker_times:             # 等效于 Go 代码的：(int(math.Sqrt(float64(m/t*8+1))) - 1) / 2             count = (int(math.isqrt(m // t * 8 + 1)) - 1) // 2             left_h -= count             if left_h <= 0:                 returnTrue         returnFalse     left, right = 1, max_t * h * (h + 1) // 2     while left < right:         mid = (left + right) // 2         if can_finish(mid):             right = mid         else:             left = mid + 1     return left if __name__ == "__main__":     mountain_height = 4     worker_times = [2, 1, 1]     result = min_number_of_seconds(mountain_height, worker_times)     print(result)