首页 > ACM题库 > HDU-杭电 > hdu 2021 发工资咯:)-贪心-[解题报告]C++
2013
12-26

hdu 2021 发工资咯:)-贪心-[解题报告]C++

发工资咯:)

问题描述 :

作为杭电的老师,最盼望的日子就是每月的8号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵
但是对于学校财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小胡老师最近就在考虑一个问题:如果每个老师的工资额都知道,最少需要准备多少张人民币,才能在给每位老师发工资的时候都不用老师找零呢?
这里假设老师的工资都是正整数,单位元,人民币一共有100元、50元、10元、5元、2元和1元六种。

输入:

输入数据包含多个测试实例,每个测试实例的第一行是一个整数n(n<100),表示老师的人数,然后是n个老师的工资。
n=0表示输入的结束,不做处理。

输出:

输入数据包含多个测试实例,每个测试实例的第一行是一个整数n(n<100),表示老师的人数,然后是n个老师的工资。
n=0表示输入的结束,不做处理。

样例输入:

3
1 2 3
0

样例输出:

4

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2021

#include <stdio.h>

int main(void)
{
    int n, i, x, sum;
    
    while (scanf("%d", &n), n)
    {
        sum = 0;
        for (i = 0 ; i < n ; i++)
        {
            scanf("%d", &x);
            sum += x / 100;
            x %= 100;
            sum += x / 50;
            x %= 50;
            sum += x / 10;
            x %= 10;
            sum += x / 5;
            x %= 5;
            sum += x / 2;
            x %= 2;
            sum += x;
        }
        printf("%d\n", sum);
    }

    return 0;
}

解题转自:http://blog.csdn.net/basementman/article/details/16925611


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的