LC 2952. 需要添加的硬币的最小数量

https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/description/

题解写的非常好，就是使用归纳法:

假设我们已经收集了 `[1, s)` ，然后遇到下一个元素是X
如果 `x > s` 的话，那么从 `[s, x)` 中间就会出现空档, 没有办法覆盖到。我们需要先收集 `s`
如果 `x <= s` 的话，那么没有问题，我们覆盖的范围就到了 `[1, s + x)`.

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        ans, s, i = 0, 1, 0
        while s <= target:
            if i < len(coins) and coins[i] <= s:
                s += coins[i]
                i += 1
            else:
                s += s
                ans += 1
        return ans