题目要求: 你就要去购物了,现在你手上有N种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出1到X之间的任意值。 输入 第一行两个数X、N,以下N个数,表示每种硬币的面值。 输出 最少需要携带的硬币个数,如果无解输出-1. 样例输入 Copy 20 4 1 2 5 10 样例输出 Copy 5 提示 每种硬币的面值可以是任意正整数1 2 3 4 5…但题目不保证是按顺序给出
解题思路: 待理解。
通关代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int max, n, value;
vector<int> coin;
cin >> max >> n;
for (int i = 0; i < n; i++) {
cin >> value;
coin.emplace_back(value);
}
sort(coin.begin(), coin.end());
if (coin[0] != 1) {
cout << -1;
return 0;
}
//
int sum = 1, ans = 1;
while (max > sum){
for (int i = n - 1; i >= 0; i--){
if (coin[i] <= sum + 1) {
ans++;
sum += coin[i];
break;
}
}
}
//
cout << ans;
return 0;
}
未毕。