POJ3040项目里，如何为奶牛分配薪酬？

本文共计1079个文字，预计阅读时间需要5分钟。

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

思路：这个题目做了两天，丢脸了...

题意：
有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的部分的钱是最少的，正确性的前提是 硬币之间的倍数关系，还有就是存在优化，就是同样的一次可以同时开出好几周的工资，这个在写的时候自己去想吧，还有这个题目要明确一个问题，就是硬币之间没有什么关系，就是每个硬币只要保证尽量浪费的少就行了。