首页 › 题库 › C/C++编程考级 › C/C++编程二级 › 简答题
简答题 偏难
#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 &lt;stdio.h&gt; #include &lt;limits.h&gt;  // 用于INT_MAX int main() {     long long n, a, b, c;     scanf("%lld", &amp;n);     scanf("%lld %lld %lld", &amp;a, &amp;b, &amp;c);     int min_count = INT_MAX;  // 初始化最小硬币数为最大整数     // 枚举c硬币的数量,最多不超过10000个     for (int x = 0; x * c &lt;= n &amp;&amp; x &lt;= 10000; x++) {         long long rem1 = n - x * c;  // 使用x个c后剩余的金额         if (rem1 &lt; 0) {             break;         }         // 枚举b硬币的数量,最多不超过10000个         for (int y = 0; y * b &lt;= rem1 &amp;&amp; y &lt;= 10000; y++) {             long long rem2 = rem1 - y * b;  // 使用y个b后剩余的金额             if (rem2 &lt; 0) {                 break;             }             // 检查剩余金额是否能被a整除             if (rem2 % a == 0) {                 int z = rem2 / a;  // a硬币的数量                 int total = x + y + z;    // 总硬币数                 // 更新最小硬币数                 if (total &lt; min_count) {                     min_count = total;                 }             }         }     }     // 若仍为初始值,说明无法凑出,否则输出最小硬币数     if (min_count == INT_MAX) {         printf("-1\n");     } else {         printf("%d\n", min_count);     }     return 0; }</pre>
这道题暂未补解析。