洛谷P2001 硬币的面值 题解
题目链接：P2001 硬币的面值
题意：
小 A 有 $n$ 种硬币，现在要买一样不超过 $m$ 元的商品，他不想得到找钱（多脏啊），同时又不想带太多的硬币，且硬币可以重复，现在已知这 $n$ 种硬币的价值，请问最少需要多少硬币就能组合成所有可能的价格？
输入格式：
第一行两个数：$n, m$。
下一行，共 $n$ 个数字，表示硬币的面值。
输出格式：
一行一个数，表示最少需要多少硬币。如果无解请输出
No answer!!!。数据范围：
$1 \le n \le 2 \times {10}^5,~1 \le m \le 2^{63}$。
首先如果面额里没有 $1$ ，那一定无解，否则一定有解。
考虑将所有面额（包括 $m$）从小到大排序，依次每个 $a_i$ 到 $a_{i+1}$ 的贡献
容易发现，如果我们当前可以覆盖区间 $[1,x]$ 且 $a_i \le x+1$ ，那我们也能覆盖 $[1,x+ka_i]$ 。
而当 $x + ka_i + 1\ge a_{i+1}$ 时，我们已经没有必要再使用 $a_i$ 了，因为此时 $a_{i+1}$ 能覆盖的更远
我们只需要维护 $x$ 和硬币总数，直到超过 $m$ 即可。
时间复杂度 $\mathcal{O}(n \log n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e6 + 15))
int a[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int n,m; cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = m; sort(a + 1, a + 1 + n + 1);
if(a[1] != 1) return cout << "No answer!!!\n", 0;
int mx = 0, res = 0;
for(int i = 1; i <= n; i++)
if(mx < a[i + 1] - 1)
{
int x = (a[i + 1] - 1 - mx - 1) / a[i] + 1;
mx += a[i] * x; res += x;
if(mx >= m) return cout << res << '\n', 0;
}
cout << res + 1 << '\n';
return 0;
}参考文献：
