濮阳市做网站,河北seo推广公司,品牌服务推广,运营一个企业网站的推广方案Leetcode 3296. Minimum Number of Seconds to Make Mountain Height Zero 1. 解题思路2. 代码实现 题目链接#xff1a;3296. Minimum Number of Seconds to Make Mountain Height Zero
1. 解题思路
这一题的思路的话我们采用的是一个二分法的思路#xff0c;找到一个最大…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 T使得在这个时间 T T T之内所有workers移除的山的高度的总和不低于给定值 H H H。
而对于在某个给定的时间 T T T下工人 i i i能够移除的山的高度 h i h_i hi满足如下关系式 t i × h i ( h i 1 ) 2 T t_i \times \frac{h_i(h_i1)}{2} T ti×2hi(hi1)T
即有 h i − 1 1 8 T t i 2 h_i \frac{-1\sqrt{1\frac{8T}{t_i}}}{2} hi2−11ti8T
因此我们用二分法查找一下临界值即可。
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 * (r1) // 2while j-i 1:t (ij) // 2if is_possible(t):j telse:i treturn j提交代码评测得到耗时277ms占用内存17.8MB。
