POJ3040给奶牛发工资

题意：

有n种硬币，每种硬币有mi个，然后让你给奶牛发工资，每周发至少c元（就是不找零钱的意思）然后问你能发几周？（硬币之间都是倍数关系）

思路：

这个题目做了两天，丢脸，看完这个题目我的第一反应就是从大的发起，就是先花面值大的，能大的就一直大的，只要不超过c,然后再能小的就一直小的，补全没超过但是又不够那一部分，这个想法一开始就是对的，只不过我写的时候是排序，然后从前往后取，不能取了再从后往前取。。。这样一直wa，后来无奈了我看了下题解，卧槽，没错啊（这最蛋疼了，因为我敲题的错误思路和正确思路没冲突，说不清..）结果就一直以为自己姿势不对，然后不停的重新敲，优化优化优化。。还是wa，最后无奈了，直接找了个代码看看，结果...哎！说下正解吧、

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

typedef struct

{

    int a ,b;

}NODE;

NODE node[25];

bool camp(NODE a, NODE b)

{

    return a.a > b.a;

}

int minn(int x ,int y)

{

    return x < y ? x : y;

}

int main ()

{

    int n ,c ,i ,j;

    int need[25];

    while(~scanf("%d %d" ,&n ,&c))

    {

        for(i = 1 ;i <= n ;i ++)

        scanf("%d %d" ,&node[i].a ,&node[i].b);

        sort(node + 1 ,node + n + 1 ,camp);

        int ans = 0 ,l;

        for(i = 1 ;i <= n ;i ++)

        if(node[i].a >= c) ans += node[i].b;

        else break;

        if(i == n + 1)

        {

            printf("%d\n" ,ans);

            continue;

        }

        l = i;

        while(1)

        {

            memset(need ,0 ,sizeof(need));

            int s = c;

            for(i = l ;i <= n ;i ++)

            {

                need[i] = minn(node[i].b ,s / node[i].a);

                s -= need[i] * node[i].a;

            }

            if(s > 0)

            for(i = n ;i >= l ;i --)

            {

                if(node[i].b && node[i].a >= s)

                {

                    s -= node[i].a;

                    need[i] ++;

                    break;

                }

            }

            if(s > 0) break;

            int t = 1000000000;

            for(i = l ;i <= n ;i ++)

            {

                if(need[i])

                t = minn(t ,node[i].b / need[i]);

            }

            ans += t;

            for(i = l ;i <= n ;i ++)

            if(need[i]) node[i].b -= t * need[i];

        }

        printf("%d\n" ,ans);

    }

    return 0;

}

其实这个题目是个不错的贪心题，这个题目我们一定要注意，大硬币一定是小硬币的倍数，这个是关键，首先我们把所有硬币按照面值从大到小排序，比c还大的面值想都不用想，直接就加上硬币个数，然后处理其他的，我们先从大的取，能取多少取多少，就是比如你要取50块钱，然后现在有

面值 30 15 1

个数 2 5 4

这样先取的个数是 1 1 4 一共是 30*1+15*1+1*4=49

剩余个数 1 4 0 距离目标还差1块钱，然后我们在倒着取

1 15 30

0 4 1

在15的地方取一个，然后满足要求了，就行了，这样做是为了保证超出c的部分的钱是最少的，正确性的前提是硬币之间的倍数关系，还有就是存在优化，就是同样的一次可以同时开出好几周的工资，这个在写的时候自己去想吧，还有这个题目要明确一个问题，就是硬币之间没有什么关系，就是每个硬币只要保证尽量浪费的少就行了。

巴特西

POJ3040给奶牛发工资

最新文章

热门文章