发工资咯

题目描述

作为吉大的老师，最盼望的日子就是每月的9号了，因为这一天是发工资的日子，养家糊口就靠它了，呵呵

但是对于学校财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小胡老师最近就在考虑一个问题：如果每个老师的工资额都知道，最少需要准备多少张人民币，才能在给每位老师发工资的时候都不用老师找零呢？

这里假设老师的工资都是正整数，单位元，人民币一共有100元、50元、10元、5元、2元和1元六种。

输入

输入数据包含多个测试实例，每个测试实例的第一行是一个整数n（n<100），表示老师的人数，然后是n个老师的工资。

n=0表示输入的结束，不做处理。

输出

对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。

样例输入

3 1 2 3
0

样例输出

4

这道题我百度了一下，来源是杭电出的题。就这道题而言，要求总的钱的数量最小，必然每个人应该分得的钱的数量应该最小，换句话说，所有的子问题都保证最小就可以了。因此只需要先利用大面额的钱来分，当剩余钱不足当前面额时，转向下一个小面额，以此类推，知道采用1元为止。所以，利用循环结构很容易将程序写出，整体来说难度不大，只是审题需要注意一下。我写的C++代码如下：

1 #include<iostream>
 2 #include<vector>
 3 #include<algorithm>
 4 inline int cmp(const int &a, const int &b) {
 5     if (a > b)
 6         return 1;
 7     else
 8         return 0;
 9 }
10 int main() {
11     using namespace std;
12     vector<int> cashType;
13     vector<int>::iterator itCashType;
14     //data initialization
15     cashType.push_back(50);
16     cashType.push_back(100);
17     cashType.push_back(10);
18     cashType.push_back(5);
19     cashType.push_back(1);
20     cashType.push_back(2);
21     sort(cashType.begin(), cashType.end(), cmp);
22     //get input data
23     int n;        //total teachers
24     int i;
25     int tmpIncome;
26     int totalNumOfCash;
27     vector<int> teachers;
28     vector<int>::iterator itTeachers;
29     for (;;) {
30         cin >> n;
31         if (n == 0) break;
32         for (i = 0; i < n; i++) {
33             cin >> tmpIncome;
34             teachers.push_back(tmpIncome);
35         }
36         //processing
37         totalNumOfCash = 0;
38         for (itTeachers = teachers.begin(); itTeachers != teachers.end(); itTeachers++) {
39             for (itCashType = cashType.begin(); itCashType != cashType.end(); itCashType++) {
40                 //
41                 while (*itTeachers >= *itCashType) {
42                     *itTeachers -= *itCashType;
43                     totalNumOfCash++;
44                 }
45             }
46         }
47         cout << totalNumOfCash << endl;
48     }
49     return 0;
50 }

还是提及一下STL中vector如何遍历元素，这里使用了迭代器的方法。对于STL容器而言，使用迭代器（iterator）遍历容器中的数据，是一种通用的方法（比如map set等利用红黑树实现的容器，不可能利用索引，也就是传统的数组的下标，来访问容器中的元素）。迭代器可以看作是一个指针，确定首尾（容器的begin() end()方法）

就可以使用迭代器了。

这里还有一道类似的题目，列举出来供参考：

你是一个土豪，于是你决定发行自己的钱币。考虑到你是一个土豪，传统的一角，五毛，一块，五元，十块，五十元，一百块的币种机制，会让你印太多太多的钱币，这就很费纸，非常不环保。（你想100,000,000得多少张纸？嗯，没错，你是一个土豪……）

后来一天睡醒之后，你梦到一个数字P。于是你有了一个好注意：你的银行只发行P的次方的面值的纸币。意思是，你的银行只发行1, P，P^2, P^3, P^4 ...面额的纸币。（^表示指数，不是C语言中的异或）。

对于一个给定的P，当来了另一个土豪，想取款Q元时，你能否算出，你的银行最少需要给这位土豪多少张钱呢？

Input:

第一行一个整数T，表示数据组数。(T < 500)

每组数据只有一行，包含两个数P，Q(0 < P,Q <= 10000)

Output:

对于每组输入，输出一个整数，表示银行最少要给的钱的张数。

Sample Input:

3

2 9

3 9

4 9

Sample Output:

2

1

3
原文链接: https://www.cnblogs.com/ggggg63/p/6358193.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍