首页 > 试题广场 >

发工资

[编程题]发工资

热度指数：779 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于财务处的工作人员来说，发工资那天是最忙碌的。财务处的NowCoder最近在考虑一个问题：如果每个员工的工资额都知道，最少需要准备多少张人民币，才能在给每位同事发工资的时候都不用找零呢？
这里假设员工的工资都是正整数，单位元，人民币一共有100元、50元、20元、10元、5元、2元和1元七种。

输入描述:

输入数据包含多个测试实例，每个测试实例的第一行是一个整数n (n≤100)，表示人数，然后是n个员工的工资。

输出描述:

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

示例1

输入

3
1 2 3
3
100 200 300

输出

4
6

算法知识视频讲解

Java

詆調壹點

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// 要用贪心做,动态规划会越界
		Scanner sc = new Scanner(System.in);
		int money[] = {100, 50, 20, 10, 5, 2, 1};
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int sum = 0;
			for (int i = 0; i < n; i ++ ) {
				int m = sc.nextInt();
				for (int j = 0; j < money.length; j ++ ) {
					sum += m / money[j];
					m = m % money[j];
					if(m == 0) break;
				}
			}
			System.out.println(sum);
		}
	}
}

发表于 2016-10-13 03:36:09 回复(0)