已知你有 a 张 1 块钱,b 张 2 块钱,求你最小的不能支付的价钱(不包括0)。 输入格式: 两个正整数 a 和 b(0≤a,b≤10 5 ) 输出格式: 输出最小的不能支付的价钱 ,用c语言解题
时间: 2024-10-21 20:10:02 浏览: 40
七年级上册数学第三次月考试题_1.docx
这个问题可以使用贪心算法来解决。由于你需要找到最小的不能支付的金额,你可以从最大的面额开始考虑,即2块钱的硬币。如果你的硬币组合中包含了所有2块的硬币,那么接下来就是看1块的硬币是否足够组成大于当前最大金额的倍数,因为不可能有一张单独的1块钱不足以构成新的组合。
如果a张1块钱的硬币不足以组成2块的整数倍,那么你就找到了最小的不能支付的金额,它是2减去a除以2的余数(如果余数不为0)。因为a最多只有105张,所以计算不会超出范围。
以下是用C语言的一个简单实现:
```c
#include <stdio.h>
int main() {
int a, b;
// 输入
scanf("%d %d", &a, &b);
// 检查最小的不能支付的金额
if (a == 0 && b >= 2) {
printf("1\n");
} else if (b >= a) { // 如果有足够的2块硬币,直接检查1块的剩余价值
int min_price = 2 - (a / 2); // 最小需要补足的2的倍数差额
if (min_price > 0)
printf("%d\n", min_price);
else
printf("0\n");
} else { // 如果2块硬币不够,先用2块凑成尽可能大的整数,然后看剩下的1块能否支付
for (int i = b; i >= 1; i--) { // 从b到1枚枚试
if (i * 2 <= a) { // 能否组成2的倍数
a -= i * 2;
if (a == 0) { // 如果凑够了,最小不能支付的就是之前剩下的
printf("1\n");
break;
}
// 再看剩余的1块钱是否能组成其他整数,直到不足以形成2的倍数
for (int j = a; j >= 1; j--) {
if (j <= i) {
printf("1\n");
break;
}
}
return 0; // 找到了最小不能支付的,结束程序
}
}
printf("2\n"); // 如果1块都不能组成2的倍数,说明最小不能支付的是2
}
return 0;
}
```
阅读全文