题目描述

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

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

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

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

样例

输入：coins = [1,4,10], target = 19
输出：2
解释：需要添加面值为 2 和 8 的硬币各一枚，得到硬币数组 [1,2,4,8,10]。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 2。

输入：coins = [1,4,10,5,7,19], target = 19
输出：1
解释：只需要添加一枚面值为 2 的硬币，得到硬币数组 [1,2,4,5,7,10,19]。
可以证明从 1 到 19 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 1。

输入：coins = [1,1,1], target = 20
输出：3
解释：
需要添加面值为 4、8 和 16 的硬币各一枚，得到硬币数组 [1,1,1,4,8,16]。 
可以证明从 1 到 20 的所有整数都可由数组中的硬币组合得到，且需要添加到数组中的硬币数目最小为 3。

限制

• 1 <= target <= 10^5
• 1 <= coins.length <= 10^5
• 1 <= coins[i] <= target

算法

(思维题) $O(n \log n + \log target)$

1. 假设当前的组合可以组成 $1$ 到 $t$ 的所有整数，当给定一个新的硬币 $c$ 时，如果 $c \le t + 1$，则可以组成的数组范围是 $1$ 到 $t + c$；否则，这个硬币不能直接加入到组合中，需要一个面值为 $t+1$ 的硬币，将组合的范围提升到 $1$ 到 $2t + 1$ 后再次判断。
2. 根据以上思路，可以先将硬币从小到大排序，然后让 $t$ 为 $0$，开始不断循环以上过程，直到 $t$ 达到 $target$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 遍历所有硬币的时间复杂度为 $O(n)$，另外在遍历完所有硬币的情况下不超过 $O(\log target)$ 次遍历就可以让 $t$ 达到 $target$。
• 故总时间复杂度为 $O(n \log n + \log target)$。

空间复杂度

• 需要 $O(\log n)$ 的额外空间存储排序的系统栈。

C++ 代码

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        const int n = coins.size();

        int i = 0, t = 0, ans = 0;
        while (t < target) {
            if (i < n && t + 1 >= coins[i]) {
                t += coins[i];
                ++i;
            } else {
                ++ans;
                t += t + 1;
            }
        }

        return ans;
    }
};