主要是提交不了
原题链接：9742.Greedy Change
2026-03-11 21:42:19
发布于：广东
5阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> coins(n);
for (int i = 0; i < n; i++) {
cin >> coins[i];
}
// 从最大面值开始，贪心算法
vector<int> greedy_result(1000005, 0);
vector<int> optimal_result(1000005, 0);
// 预处理：计算每个金额的最优解
for (int i = 1; i <= 1000000; i++) {
optimal_result[i] = i; // 最坏情况：全用1元硬币
for (int j = 0; j < n; j++) {
if (coins[j] <= i) {
optimal_result[i] = min(optimal_result[i], optimal_result[i - coins[j]] + 1);
}
}
}
// 计算贪心算法结果
for (int i = 1; i <= 1000000; i++) {
greedy_result[i] = 0;
int temp = i;
for (int j = 0; j < n; j++) {
greedy_result[i] += temp / coins[j];
temp %= coins[j];
}
}
// 寻找第一个贪心算法不最优的金额
for (int i = 1; i <= 1000000; i++) {
if (greedy_result[i] > optimal_result[i]) {
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
这里空空如也
有帮助，赞一个