Leetcode-2952-需要添加的硬币的最小数量-c++

题目详见https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/

题解

对于正整数 $x$，如果区间 $[1,x-1]$ 内的所有金额都可取得，且$x$在数组中，则区间 $[1,2x-1]$ 内的所有金额也都可取得。证明如下。

对于任意 $1\le y<x$，$y$ 可取得，$x$ 在数组中，因此 $y+x$ 也可取得，区间 $[x+1,2x-1]$（即区间 $[1,x-1]$ 内的每个金额加上 $x$ 之后得到的区间）内的所有金额也可取得，由此可得区间 $[1,2x-1]$ 内的所有金额都可取得。

题解说的比较拗口，说几点我的想法

1. 当我们有$x_1,x_2,x_3$ 三种硬币时，我们实际上有$2^3-1$种硬币，因为我们可以把不同硬币捆绑在一起形成面值不同的新硬币。
2. 但是我们要添加最少的硬币，所以我们希望用最简单的拼法得到最大的面值，这也是为什么选择$x$与$2x$的原因。
3. 一定可以得到至少一枚一元硬币，因为想得到一元硬币只能用一个一元硬币。

注释代码

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int ans = 0;
        int x = 1;	// 初始化最开始不可得到的最小金额，最开始一元也得不到。
        int length = coins.size(), index = 0;
        while(x <= target){	// 目前不可得到的最小金额小于等于目标金额。
        	// 为什么等于也不行？因为x是‘目前不可得到的’（很蠢的问题，但我确实这么问了，就记录下来...）
            if(index < length && coins[index] <= x){
                x += coins[index];
                index++;
            }
            else{
                x <<= 1;	// x = x << 1，其实<<= 就和 *=, += 一样
                ans++;
            }
        }
        return ans;
    }
};

笔者也在新手学习期中，所写的内容主要与大家交流学习使用，如有发现任何问题敬请指正！