【题目来源】
https://www.luogu.com.cn/problem/P2001

【题目描述】
小 A 有 n 种硬币，现在要买一样不超过 m 元的商品，他不想得到找钱（多脏啊），同时又不想带太多的硬币，且硬币可以重复，现在已知这 n 种硬币的价值，请问最少需要多少枚硬币就能组合成所有可能的不超过 m 元的价格？

【输入格式】
第一行两个数：n，m。
下一行，共 n 个数字，表示硬币的面值。

【输出格式】
一行一个数，表示最少需要多少硬币。如果无解请输出 No answer!!!。

【数据范围】
对于 20% 的数据，1≤n≤10，1≤m≤100。
对于 60% 的数据，1≤n≤1000，1≤m≤10000。
对于 80% 的数据，1≤n≤30000，1≤m≤2×10^9。
对于 100% 的数据，1≤n≤2×10^5，1≤m≤2^63。

【输入样例】
5 31
1 2 8 4 16

【输出样例】
5

【算法分析】
● 注意本题是买不超过 m 元的商品，而不是买恰好等于 m 元的商品。且问的是已知 n 种币值的前提下，最少需要多少枚硬币能组合成所有可能的价格。显然，若没有面值为 1 的硬币，就不可能组成所有可能的价格，故此时按题意直接输出“No answer!!!”。

● 快读：https://blog.csdn.net/hnjzsyjyj/article/details/120131534

int read() { //fast read
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9') { //!isdigit(c)
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9') { //isdigit(c)
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

● 最少硬币问题能否使用贪心法，跟硬币的面值有关。在给定的硬币面值中，若任一面值的硬币，大于比它面值小的硬币的面值和，便可以使用贪心法。

【算法代码】← 80分代码，后续完善

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=2e5+5;
LL a[maxn];
int flag;
LL x=1,ans=1,pos=1;
LL n,m;

LL read() { //fast read
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9') { //!isdigit(c)
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9') { //isdigit(c)
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    n=read(), m=read();
    for(int i=1; i<=n; i++) {
        a[i]=read();
        if(a[i]==1) flag=1;
    }
    if(flag==0) {
        cout<<"No answer!!!";
        return 0;
    }
    sort(a+1,a+n+1);
    while(1) {
        if(pos==n) {
            ans+=(m-x)/a[pos];
            if((m-x)%a[pos]!=0) ans++;
            cout<<ans<<endl;
            return 0;
        }
        for(int i=pos; i<=n+1; i++) {
            if(a[i]>x+1||i>n) {
                pos=i-1;
                x+=a[pos];
                ans++;
                break;
            }
        }
        if(x>=m) {
            cout<<ans<<endl;
            return 0;
        }
    }
}

/*
in:
5 31
1 2 8 4 16

out:
5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/146540859
https://www.luogu.com.cn/problem/solution/B3635
https://www.luogu.com.cn/problem/solution/P2001?page=2
https://www.cnblogs.com/ShineEternal/p/10834281.html
https://blog.csdn.net/weixin_50624971/article/details/114649170