题目:2952. 需要添加的硬币的最小数量
思路:假设区间[1,s-1]的数都可组合得到,当遍历到x=coins[i]时,
1、当x<=s时,可以组合的数就是区间[1,s-1]和区间[x,s-1+x]的交集,即区间[1, s-1+x]
2、当x>s时,区间[1,s-1]和区间[x,s-1+x]没有交集,那我就只能通过添加一个数来实现了。在这里添加元素s,可得到的新区间为[s,2s-1],和旧区间组合就是[1,2s-1]
具体细节看注释
class Solution {
public:
int minimumAddedCoins(vector<int>& coins, int target) {
//先升序排序
sort(coins.begin(),coins.end());
int ans=0;
//s是目前得不到的数
int s=1,i=0;
while(s<=target){
//第一种情况
if(i<coins.size()&&coins[i]<=s){
s+=coins[i++];
}else{
//第二种情况
s*=2;
ans++;
}
}
return ans;
}
};
标签:int,coins,++,添加,ans,区间,LeetCode,2952,nice
From: https://blog.csdn.net/weixin_46028214/article/details/140804455