一、题目
1、题目描述
给你一个下标从 0 开始的整数数组
coins，表示可用的硬币的面值，以及一个整数target。如果存在某个
coins的子序列总和为x，那么整数x就是一个 可取得的金额 。返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围
[1, target]内的每个整数都属于 可取得的金额 。数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。
2、接口描述
cpp
class Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
}
};python3
class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:3、原题链接
二、解题报告
1、思路分析
对于一个区间[0, r],我们想要假如某个数x使得区间扩大并且仍然连续，x需要满足什么条件呢？
如果x <= r + 1，那么加入x后区间变为[0, r + x]
当x为r + 2时，区间变为[0, r] U [r + 2, 2r + 2]
所以我们想要区间扩大并连续，加入的x必须满足小于等于r + 1
将原数组预排序，考虑初始区间为[0, 0]，右边界记为r
遍历数组，如果当前数字小于等于r + 1，那么加入区间，扩展右边界
否则需要我们手动加入数字，直接加最大的r + 1，同时维护增加次数
2、复杂度
时间复杂度： O(nlogn)空间复杂度：O(1)
3、代码详解
cpp
class Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
sort(coins.begin(), coins.end());
int ret = 0;
for(int n = coins.size(), r = 0, p = 0; r < target; ){
if(p < n && coins[p] <= r + 1)
r += coins[p++];
else
r += r + 1, ret++;
}
return ret;
}
};python3
class Solution:
def minimumAddedCoins(self, coins: List[int], target: int) -> int:
ret, r, i = 0, 0, 0
coins.sort()
while r < target:
if i < len(coins) and coins[i] <= r + 1:
r += coins[i]
i += 1
else:
r += r + 1
ret += 1
return ret
