0
已解决
中级天翼
1801 换小额钞票
题目描述 Description
小明妈妈是开超市的，每天都要卖很多东西，需要准备很多零钱，某一天超市零钱不够了，于是她去银行换钞票，想把n张100元的钞票兑换成10元、20元、50元小钞票形式。请问有多少种兑换的方式呢？
输入描述 Input Description
100元的钞票的数量n张（1<=n<=10000）
输出描述 Output Description
多少种换法
样例输入 Sample Input
1
样例输出 Sample Output
10
1
已采纳
资深天翼
因为100的倍数一定是50的倍数，我们可以从一共有多少个50元来考虑，最小的情况可能是有0个50元，最多的情况可能是有n*100/50个50元
而每个50元可以拆成①10+10+10+10+10，②20+20+10，③ 20+10+10+10三种情况，100元的话可以拆成100/20+1共六种情况，150元的话可以拆成150/20+1共8中情况，以此类推。。。
所以最外层循环是50元的个数，从0到n*100/50，循环内，我们计算不是50元的那部分钱可以拆成多少种情况，然后累加起来得到最终结果
n*=100;
for(int i=0; i<=n/50; i++)
{
ans+=(n-i*50)/20+1;
}
最后输出ans即可。
0
缔造者
1
