HrbustOJ 1167 每种面值的货币要多少

发表于 | 分类于 | 阅读次数: |
字数统计: 464 | 阅读时长 ≈ 2

每种面值的货币要多少

Time Limit: 1000 MS Memory Limit: 65536 K

Total Submit: 596(357 users) Total Accepted: 370(335 users) Rating: Special Judge: No

Description

组织终于发工资了，等了好久的工资终于来了。。。
为了让大家能在领工资的时候能尽量快，组织决定一次发完所有工资，不会出现让员工找零的情况，也就是说，如果一个员工的工资是1160元，就会给11张100元，1张50元，1张10元，而不会给员工1200元，然后让员工找40元零钱的情况。
员工的工资都是整数，单位是元，并且市面上流通的RMB面值有100元，50元，20元，10元，5元，1元。
要求最终需要的纸币张数最少。

Input

有多组测测试数据，每组测试数据占一行。
对于每组测试数据，第一个数n表示组织有多少员工，接下来有n个数，表示每一个员工要发多少工资。
处理到文件结束。
1 <= n <= 100000， 每个员工的工资不超过1000000

Output

每行输出6个数，表示100元、50元、20元、10元、5元、1元各需要多少张。
答案可能有0。

Sample Input

1 701
3 474 808 212

Sample Output

7 0 0 0 0 1
14 1 1 1 1 9

Author

黄李龙

题解

贪心问题，每次都选最大面额的。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <cstring>
#include <malloc.h>
#include <cstdio>
#include <algorithm>

using namespace std ;

int money[6] = {100 , 50 , 20 , 10 , 5 , 1} ;

int main(){
    int n , money_ ;
    while ( cin >> n ){
        int cost[6] = {0} ;
        for ( int i = 0 ; i < n ; i ++ ){
            cin >> money_ ;
            for ( int j = 0 ; j < 6 ; j ++ ){
                cost[j] += money_ / money[j] ;
                money_ %= money[j] ;
            }
        }
        for ( int i = 0 ; i < 6 ; i ++ ){
            i == 0 || cout << " " ;
            cout << cost[i] ;
        }
        cout << endl ;
    }
    return 0 ;
}