题解-需要添加的硬币的最小数量-最大化在缺口处补硬币的作用

Problem: 100153. 需要添加的硬币的最小数量

思路

• 这题和LeetCode-1798. 你能构造出连续值的最大数目很像,很经典的想法
• 是子序列所以先排序
• 先考虑我们手里的硬币能构造出来多少
• 假设我们手里的硬币足够我们构造出来[0,x),接下来我们又拿到了一个硬币,数值为y,
  • 如果我们把y放进之前的所有序列之中,会发现我们能够构造[y,x+y)
  • 再加上刚才的区间,我们手里的硬币加y之后能构造的数的范围为$[0,x)\bigcup[y,x+y)$
  • 如果y<=x则我们能够构造的数就能达到[0,x+y)
  • 如果y>x则会有一段空缺
• 为了填补这段空缺,我们应该往里面放另一块硬币,假设为z,根据上面的推论,我们很容易得到z会生成的片段为[z,x+z),而且z的取值范围应该为[y-x,x],为了让填补有效,且最大化填补的内容,应该让z=x,因为这样能最大化填补的空缺
  • 取最大更有可能单次填补完空缺
• 而我们遇到的问题只是将y换成了target,所有遇到的大于当前x的也认为是y即可

Code

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        res=0
        canMake=0 #能生成的范围是[0,canMake]
        i=0
        while i<(len(coins)):
            val=coins[i]
            if val<=canMake+1:
                canMake+=val
                i+=1
            else:
                res+=1 #这里补的硬币就是canMake+1
                canMake+=canMake+1
        while canMake<target:
            res+=1
            canMake+=canMake+1
        return res