问题描述
Problem Description
作为杭电的老师,最盼望的日子就是每月的8号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵
但是对于学校财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小胡老师最近就在考虑一个问题:如果每个老师的工资额都知道,最少需要准备多少张人民币,才能在给每位老师发工资的时候都不用老师找零呢?
这里假设老师的工资都是正整数,单位元,人民币一共有100元、50元、10元、5元、2元和1元六种。
Input
输入数据包含多个测试实例,每个测试实例的第一行是一个整数n(n<100),表示老师的人数,然后是n个老师的工资。 n=0表示输入的结束,不做处理。
Output
对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。
Sample Input
3
1 2 3
0
Sample Output
4
问题分析
Problem Analyse
本题是为C语言初学者提供的。
Algorithm Analyse
这道题可以简化为给定面额,求需要的人民币的张数。
用的方法是贪心。这不难理解,用的人民币的面值越大,当然张数就越少。
算法实现
求某一面额的张数,用的方法是整除求余法。比如325块钱需要几张100块。就是325 / 100 = 3 … 25即三张100,余下25元。
参考源码
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
int main(void) | |
{ | |
int n, i, j, x, sum; | |
int money[] = { 100, 50, 10, 5, 2, 1 }; | |
while (scanf("%d", &n), n) { | |
sum = 0; | |
for (i = 0 ; i < n ; i++) { | |
scanf("%d", &x); | |
for (j = 0; x; j++) { | |
sum += x / money[j]; | |
x %= money[j]; | |
} | |
} | |
printf("%d\n", sum); | |
} | |
return 0; | |
} |