简答题
偏难
#13144
硬币 可以使用任意数量的 a元硬币、b 元硬币和 c 元硬币。请找出恰好凑出 n 元所需的最小硬币总数。若无法凑出,则输出 -1。 时间限制:1000ms,内存…
硬币
可以使用任意数量的 a元硬币、b 元硬币和 c 元硬币。请找出恰好凑出 n 元所需的最小硬币总数。若无法凑出,则输出 -1。
时间限制:1000ms,内存限制:256MB
输入格式
第一行,整数 n;
第二行,三个整数表示 a、b、c。
输出格式
输出最小硬币总数(若无法凑出则输出 -1)。
输入样例#1
100 20 40 50
输出样例#1
2
输入样例#2
99 1 5 10
输出样例#2
14
数据范围:
1≤N≤109;1≤A≤B≤C≤109。保证最终最小硬币总数不超过104。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <stdio.h>
#include <limits.h> // 用于INT_MAX
int main() {
long long n, a, b, c;
scanf("%lld", &n);
scanf("%lld %lld %lld", &a, &b, &c);
int min_count = INT_MAX; // 初始化最小硬币数为最大整数
// 枚举c硬币的数量,最多不超过10000个
for (int x = 0; x * c <= n && x <= 10000; x++) {
long long rem1 = n - x * c; // 使用x个c后剩余的金额
if (rem1 < 0) {
break;
}
// 枚举b硬币的数量,最多不超过10000个
for (int y = 0; y * b <= rem1 && y <= 10000; y++) {
long long rem2 = rem1 - y * b; // 使用y个b后剩余的金额
if (rem2 < 0) {
break;
}
// 检查剩余金额是否能被a整除
if (rem2 % a == 0) {
int z = rem2 / a; // a硬币的数量
int total = x + y + z; // 总硬币数
// 更新最小硬币数
if (total < min_count) {
min_count = total;
}
}
}
}
// 若仍为初始值,说明无法凑出,否则输出最小硬币数
if (min_count == INT_MAX) {
printf("-1\n");
} else {
printf("%d\n", min_count);
}
return 0;
}</pre>
这道题暂未补解析。