2952 需要添加的硬币的最小数量（Medium）

这道题止中等？

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 $[1, target]$ 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

示例 1：

输入：coins = [1,4,10], target = 19

输出：2

解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10] 。

可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2 。

自己想没想出来

官方解：贪心算法

为方便描述，把 0也算作可以得到的数。

假设现在得到了区间 $[0,s−1]$ 中的所有整数，如果此时遍历到整数 $x=coins[i]$，那么把 $[0,s−1]$ 中的每个整数都增加 x，我们就得到了区间 $[x,s+x−1]$ 中的所有整数。

把 coins 从小到大排序，遍历 $x=coins[i]$。分类讨论，看是否要添加数字：

  • 如果 x≤s，那么合并 $[0,s−1]$ 和 $[x,s+x−1]$这两个区间，我们可以得到 $[0,s+x−1]$ 中的所有整数。
  • 如果 x>s，或者遍历完了 coins 数组，这意味着我们无法得到 s，那么就一定要把 s 加到数组中（加一个比 s 还小的数字就没法得到更大的数，不够贪），这样就可以得到了 $[s,2s−1]$ 中的所有整数，再与 $[0,s−1]$ 合并，可以得到 $[0,2s−1]$ 中的所有整数。然后再考虑 x 和 2s 的大小关系，继续分类讨论。
    当 s>targets 时，我们就得到了 $[1,target]$ 中的所有整数，退出循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumAddedCoins(int[] coins, int target) {
        Arrays.sort(coins);
        int ans = 0, s = 1, i = 0;
        while (s <= target) {
            if (i < coins.length && coins[i] <= s) {
                s += coins[i++];
            } else {
                s *= 2; // 必须添加 s
                ans++;
            }
        }
        return ans;
    }
}