题目

某单位给每个员工发工资（精确到元）。为了保证避免临时兑换零钱，且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值（100,50,20,10,5,2,1元共七种）的张数，请编程完成。

思想

贪心

C++代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){
    int n, gz;
    int b[8] = {0, 100,50, 20, 10, 5, 2, 1};
    int s[8] = {0, 0, 0, 0, 0, 0, 0, 0};
    cin >> n;
    for(int i = 1; i <= n; i ++){
        memset(s, 0, sizeof s);//清空s数组
        cin >> gz;
        for(int j = 1; j <= 7; j ++){
            int a = gz / b[j];
            s[j] += a;
            gz -= a * b[j];  
        }

        for(int i = 1; i <= 7; i ++){
            cout << b[i] << "---" << s[i] << endl;
        }
        cout << endl;
    }

    return 0;
}

样例输入

4
1200 11 25 30

样例输出

100---12
50---0
20---0
10---0
5---0
2---0
1---0

100---0
50---0
20---0
10---1
5---0
2---0
1---1

100---0
50---0
20---1
10---0
5---1
2---0
1---0

100---0
50---0
20---1
10---1
5---0
2---0
1---0