《算法笔记》codeup 100000584 问题 G: 找零钱

思路：

本题同问题D及问题F类似，尽可能地按面额从大到小找钱即可解决。

解答：

/*
《算法笔记》codeup 100000584 问题 G: 找零钱
*/#include <cstdio>
using namespace std;int main() {int amount;                                         // 总额int denomination[5] = {50, 20, 10, 5, 1};           // 面额while (scanf("%d", &amount) != EOF) {for (int i = 0; i <= 4; i++) {if (amount < denomination[i])               // 跳到比总额小的面额{continue;}int num = amount / denomination[i];         // 计算总额包含多少张当前选中的面额int balance = amount % denomination[i];     // 计算余额if (num > 0)                                // 如果张数不为0，则{                                               printf("%d*%d", denomination[i], num);  // 输出amount = balance;                       // 置下一次需要计算的金额为余额}else                                        // 如果张数为0，则{break;                                  // 结束}if (amount > 0)                             // 如果下一次需要计算的金额不为0，则{printf("+");                            // 输出一个+}}printf("\n");}return 0;
}