LCS 01-下载插件

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:27:09 2023-09-13 11:27:09 Updated    

小扣打算给自己的 VS code 安装使用插件，初始状态下带宽每分钟可以完成 1 个插件的下载。假定每分钟选择以下两种策略之一: -
使用当前带宽下载插件 - 将带宽加倍（下载插件数量随之加倍） 请返回小扣完成下载 n 个插件最少需要多少分钟。 注意：实际的下载的插件数量可以超过
n 个 示例 1： >输入：n = 2 > >输出：2 > >解释： > 以下两个方案，都能实现 2 分钟内下载 2 个插件 >-
方案一：第一分钟带宽加倍，带宽可每分钟下载 2 个插件；第二分钟下载 2 个插件 >- 方案二：第一分钟下载 1 个插件，第二分钟下载 1 个插件 示例
2： >输入：n = 4 > >输出：3 > >解释： > 最少需要 3 分钟可完成 4 个插件的下载，以下是其中一种方案: >
第一分钟带宽加倍，带宽可每分钟下载 2 个插件; > 第二分钟下载 2 个插件; > 第三分钟下载 2 个插件。 提示： - 1 <= n <= 10^5

贪心算法，如果选择当前这一分钟不下载而是加倍，那么这个选择至少是跟不加倍是一样好的。举个例子，目前下载是a，这一分钟和下一分钟，下载量就是2a，加倍这一分钟和下一分钟的下载量也是0+2a = 2a。只有一种情况例外，那就是当前需要下载插件的剩余数量小于a，一分钟可以搞定，那就不需要加倍。
所以每一步判断剩余数量是不是需要超过一分钟就好了，超过一分钟，那就加倍。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def leastMinutes(self, n: int) -> int:
        
        cur = 1

        res = 0

        while n > 0:
            if n <= cur:
                n -= cur
                res += 1

            else:
                res += 1
                cur *= 2
            
        return res
 Comments
On this page
LCS 01-下载插件