移山所需的最少秒数

题目描述1

题目讲解

为什么使用二分法

假设你要把一堆石头搬完，你问朋友：

“如果给你 10 分钟，你能搬完吗？”

他能回答“能”或“不能”。

你继续问：

“那 5 分钟呢？”

你发现：

时间越长，他越可能搬完

一旦某个时间点能搬完，之后的时间都能搬完

这就是典型的“单调性 + 判断函数”，二分法的黄金搭档

具体流程

  1. 每个工人削第 1 单位高度需要 w 秒，削第 2 单位需要 2w 秒，削第 3 单位需要 3w 秒…… 也就是说，给定时间 T，最多能削多少高度：
$$ w * \frac{x(x+1)}{2} ≤ time $$
  1. 简化为
$$ limit = \frac{2 * time}{w} $$
  1. 解不等式 x(x+1) ≤ limit

求得:

$$ x = \frac{-1 + \sqrt{1 + 4 \cdot limit}}{2} $$

代码

c
java
python
from math import isqrt
from typing import List

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        H = mountainHeight
        times = workerTimes

        # 判断在 time 秒内能不能把山削完
        def can_finish(time: int) -> bool:
            total = 0
            for w in times:
                # 对于每个工人，求最大 x，使得 w * x * (x + 1) / 2 <= time
                # 即 x * (x + 1) <= 2 * time / w
                limit = (time // w) * 2  # 这里是 2T / w，先整除避免溢出
                # 解 x^2 + x - limit <= 0
                # x = floor( (-1 + sqrt(1 + 4*limit)) / 2 )
                if limit <= 0:
                    continue
                # 用整数 sqrt
                s = isqrt(1 + 4 * limit)
                x = (s - 1) // 2
                # 累加所有工人的削减量
                total += x
                if total >= H:
                    return True
            return total >= H

        left, right = 0, 10**18  # 时间上界可以取很大

        while left < right:
            mid = (left + right) // 2
            if can_finish(mid):
                right = mid
            else:
                left = mid + 1

        return left

链接

  1. 移山所需的最少秒数https://leetcode.cn/problems/minimum-number-of-seconds-to-make-mountain-height-zero/description/ ↩︎