洛谷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;
}参考文献：
