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 ≤ 03. 解这个二次不等式，最大整数 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 mainimport ( "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 mathdefmin_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 leftif __name__ == "__main__": mountain_height = 4 worker_times = [2, 1, 1] result = min_number_of_seconds(mountain_height, worker_times) print(result)
·
我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展
·
