题目

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

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

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

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

返回一个整数，表示工人们使山的高度降低到 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 <= 10^5
• 1 <= workerTimes.length <= 10^4
• 1 <= workerTimes[i] <= 10^6

解题思路

思路一：二分查找（Binary Search on Answer）

这是处理“最小化最大值”或“求满足条件的最小时间”这类问题的标准算法。

1. 算法逻辑

• 单调性判断：总工作时间 $T$ 与工人们能降低的总高度 $H_{total}$ 成正相关。时间越长，能降低的高度越多。
• 查找过程：
  1. 预设一个时间的搜索范围 $[left, right]$。
  2. 取中间值 $mid$。
  3. Check 逻辑：计算在 $mid$ 秒内，所有工人各自能降低的最大高度之和。
  4. 如果总高度 $\ge mountainHeight$，说明 $mid$ 是可行解，尝试更小的 $T$（向左收缩边界）。
  5. 反之，说明 $mid$ 时间不足，需要增加 $T$（向右收缩边界）。

2. 数学推导

对于第 $i$ 个工人，给定工作时间 $T$，求他能降低的最大高度 $x$：

$$workerTimes[i] \cdot \frac{x(x+1)}{2} \le T$$

整理为一元二次方程形式：

$$x^2 + x - \frac{2T}{workerTimes[i]} \le 0$$

利用求根公式得 $x$ 的最大整数解：

$$x = \lfloor \frac{-1 + \sqrt{1 + \frac{8T}{workerTimes[i]}}}{2} \rfloor$$

3. 复杂度分析

• 时间复杂度：$O(N \cdot \log(T_{max}))$。其中 $N$ 是工人数组长度，$\log(T_{max})$ 是对时间范围进行二分的次数。
• 空间复杂度：$O(1)$。

思路二：最小堆模拟（Priority Queue / Greedy）

这是一个基于贪心策略的模拟算法，通过动态维护每个工人完成下一单位工作的“预估完工时间”来寻找最优解。

1. 算法逻辑

• 贪心策略：由于所有工人同时工作，我们每降低 1 单位高度，都应将其分配给那个在这一单位完成后，其个人总耗时最少的工人。
• 堆结构定义：维护一个最小堆，堆中存储每个工人的状态：(next_finish_time, current_x, wt)。
  • next_finish_time：该工人完成下一单位工作后的绝对时间点。
  • current_x：该工人已经领取的降低高度的任务量。
  • wt：该工人的基础工作时间 workerTimes[i]。

2. 执行步骤

1. 初始化：将所有工人放入堆中。每个工人完成第一单位（$x=1$）的时间是 $wt$。
2. 循环迭代：执行 $mountainHeight$ 次循环：
   • 从堆顶取出 next_finish_time 最小的工人。这个值就是当前这 1 单位高度被降低时的完工时间。
   • 更新该工人的状态：
     • 已完成量 current_x 增加 1。
     • 计算该工人完成再下一单位（$current_x + 1$）所需的额外时间：$wt \cdot (current_x + 1)$。
     • 更新该工人的预估完工时间：next_finish_time = current_finish_time + wt * (current_x + 1)。
   • 将更新后的状态压回堆。
3. 结果：第 $mountainHeight$ 次出堆时的 next_finish_time 即为全局最少耗时。

3. 复杂度分析

• 时间复杂度：$O(H \cdot \log N)$。其中 $H$ 是山的高度（迭代次数），$\log N$ 是堆操作的开销。
• 空间复杂度：$O(N)$，用于存储堆。

具体代码

二分法

import math

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: list[int]) -> int:
        # check 函数：判断在 limit_time 秒内，所有工人总共能降低的高度是否 >= mountainHeight
        def check(limit_time: int) -> bool:
            total_reduced = 0
            for wt in workerTimes:
                # 根据公式：wt * x * (x + 1) / 2 <= limit_time
                # 变形得：x^2 + x - (2 * limit_time / wt) <= 0
                # 求根公式：x = (-1 + sqrt(1 + 8 * limit_time / wt)) / 2
                
                # 计算 1 + 8 * limit_time // wt
                inner_val = 1 + (8 * limit_time // wt)
                # 使用整数平方根确保大数精度
                x = (math.isqrt(inner_val) - 1) // 2
                
                total_reduced += x
                # 如果已经达标，提前返回 True 优化效率
                if total_reduced >= mountainHeight:
                    return True
            return total_reduced >= mountainHeight

        # 二分查找的范围
        # 左边界：0 秒
        # 右边界：取最慢的情况，即让最快的一个工人(min_wt)单独完成所有高度
        min_wt = min(workerTimes)
        left = 0
        right = min_wt * mountainHeight * (mountainHeight + 1) // 2
        
        ans = right
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                ans = mid      # 这个时间可行，尝试找更小的时间
                right = mid - 1
            else:
                left = mid + 1 # 时间不够，必须增加时间
                
        return ans

堆模拟法

import heapq

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: list[int]) -> int:
        # 堆里的元素: (当前如果领这一米任务的完工时间, 已经领了多少米, 基础时间wt)
        # 初始时，每个工人都领第 1 米的任务
        pq = [(wt, 1, wt) for wt in workerTimes]
        heapq.heapify(pq)
        
        max_time = 0
        # 我们一共要分配 mountainHeight 米
        for i in range(mountainHeight):
            # 谁能最快完成下一米，谁就领
            finish_time, x, wt = heapq.heappop(pq)
            
            # 记录最后一次分配的完工时间
            max_time = finish_time
            
            # 更新该工人的状态，准备好下一米的预算
            # 这个工人如果领第 x + 1 米，时间会增加 wt * (x + 1)
            next_x = x + 1
            next_finish_time = finish_time + wt * next_x
            heapq.heappush(pq, (next_finish_time, next_x, wt))
            
        return max_time