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

需要添加的硬币的最小数量

• 难度: medium
• 原始链接: https://leetcode.cn/problems/minimum-number-of-coins-to-be-added
• 标签: 数学, 贪心

解法一: 数学, 贪心

go

func minimumAddedCoins(coins []int, target int) int {
  sort.Ints(coins)
  n := len(coins)
  ans := 0
  s := 1
  i := 0
  for s <= target {
    if i < n && coins[i] <= s {
      s += coins[i]
      i++
    } else {
      ans++
      s <<= 1
    }
  }
  return ans
}