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

点击跳转题目

贪心思想，不好做，原理是如果你能得到[0,x)的所有数，那+x，你能得到[0，x)与[x,2x)中的所有数，也就是[0,2x)的所有数。
现在给你个target,你排序之后直接贪心模拟，缺一个数加一个数，当目前覆盖的范围比target大，答案就出来了。

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(),coins.end());
        int ans=0;
        int index=0;
        long long int range=1;          //range左开右闭，所以这里填1，代表目前能覆盖[0,1)区间
        while(range<=target){
            if(index<coins.size() && coins[index]<=range){          //如果当前这个数在这个范围内，最大范围就扩大到加上这个数的范围了
                range+=coins[index];
                index++;
            }
            else{                                   //如果当前这个数不在范围内，那我就得不到这个数，需要加上一个range（贪心），才能继续判断能不能得到这个数，不能再+range
                range*=2;
                ans++;
            }
        }
        return ans;
    }
};