北京市地铁建设管理公司网站百度推广平台

• Leetcode 3296. Minimum Number of Seconds to Make Mountain Height Zero
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3296. Minimum Number of Seconds to Make Mountain Height Zero

1. 解题思路

这一题的思路的话我们采用的是一个二分法的思路，找到一个最大的时间$T$，使得在这个时间$T$之内所有workers移除的山的高度的总和不低于给定值$H$。

而对于在某个给定的时间$T$下，工人$i$能够移除的山的高度$h_i$满足如下关系式：
$$t_i\times \frac{h_i(h_i+1)}{2}<=T$$

即有：
$$h_i<=\frac{-1+\sqrt{1+\frac{8T}{t_i}}}{2}$$

因此，我们用二分法查找一下临界值即可。

2. 代码实现

给出python代码实现如下：

class Solution:def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:n = len(workerTimes)r = math.ceil(mountainHeight / n)def is_possible(t):h = 0for wt in workerTimes:h += int((math.sqrt(8*t/wt + 1) - 1) / 2)return h >= mountainHeighti, j = 0, max(workerTimes) * r * (r+1) // 2while j-i > 1:t = (i+j) // 2if is_possible(t):j = telse:i = treturn j

提交代码评测得到：耗时277ms，占用内存17.8MB。