贪心去凑

C++ 代码

#include<bits/stdc++.h>

using namespace std;

int main(){

    int m,n;
    cin>>m>>n;

    vector<int> coins(n);
    for(int i = 0;i<n;i++){
        cin>>coins[i];
    }

    int cur = 0;    //当前的钱数
    int cnt = 0;    //需要的个数
    int i = 0;      //当前用第i个硬币

    if(coins[0] != 1){//必须要有1的硬币
        cout<<-1<<endl;
    }
    else{
        while(cur<m){
            while(i+1 < n && coins[i+1] <= cur+1){//凑的逻辑就是，不越界 && 当前的钱+1已经达到下一个硬币的面额，用下一个硬币来凑
                i++;
            }
            cur+=coins[i];
            cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}