【例8.1】人民币支付

解题思路

面额按 100、50、20、10、5、1 处理；每次输出金额整除面额的张数，再把金额变成余数。

正确性说明

当前面额可使用的最大张数就是整除商，剩余金额小于该面额，再处理后续面额符合尽量使用大面额的要求。

易错点

每种面额都要输出，包括零张。

复杂度

本题规模固定，时间 O(1)，额外空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int v[] = {100, 50, 20, 10, 5, 1};
    for (int x : v) {
        cout << n / x << "\n";
        n %= x;
    }
    return 0;
}