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

思路：贪心。

有时候有点搞不清楚到底用动规还是贪心。这里如果你用动规的话是找不到任何状态的，因为没有什么状态可以找，也没有什么可以递推的，因为这里是对于数组的操作，并没有让你推出根据题目而思考出这个数组的本质状态。所以这种最优问题的话，只能选贪心。

那么怎么贪心呢？这里，我们引入一个思想：如果[1,x-1]区间里面的数我们都已经得到了，这个时候，如果我们遍历到一个数i，那么这个区间的每一个数都添加i，我们就可以得到[1+i,x+i-1]的数了。

好了，我们就基于这个概念进行最优子结构推至最优结果。一开始，那当然就是空区间[0,0]，我们这个时候只得到这个区间的数。我们对于coins数组进行从小到大的排序，这样有利于我们能够不重不漏的找出需要添加的数来，而且能让数量达到最小，这一点操作还是很关键的。

然后我们令一个数x=1，开始遍历coins数组。其实就是对于[1,target]每一个数进行遍历而已，由于我们开始的时候什么数都不知道，所以需要从1开始遍历。如果说这个时候我们的遍历下标还在合法范围内，并且我们现在遍历到的数是<=x的，这说明什么？说明这个时候我们目前得到的区间是可以取这个数的，并且能把这个区间[0,0]扩大，扩大到[1,x+coins[index]+1](因为0并不在考虑范围内，我们直接就用1来表示最小的区间边界了)。然后开始遍历下一个coins的数组的元素。

但是如果我们当前遍历的数coins[index]>x是代表什么呢？说明我们区间目前得到区间的数并不能取到它，，所以我们需要让区间扩大一下，扩大至[1,2x-1],也就是让x<<=1，因为取不到，我们需要添加一个数，这个数具体是多少我们没必要关心，我们只需要知道数量就行了。那么这个时候区间的搜索范围也扩大了，再接着与coins[index]比较，看现在能不能取到它了，一直这样推下去。

上代码：

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(),coins.end());
        int n=coins.size();
        int index=0;
        int x=1;
        int count=0;
        while(x<=target){
            if(index<n&&coins[index]<=x){
             x+= coins[index++];
            }
            else
            {
                x<<=1;
                count++;
            }
        }
        return count;
    }
};