POJ3040给奶牛发工资

题意：       有n种硬币，每种硬币有mi个，然后让你给奶牛发工资，每周发至少c元（就是不找零钱的意思）然后问你能发几周？（硬币之间都是倍数关系） 思路：       这个题目做了两天，丢脸，看完这个题目我的第一反应就是从大的发起，就是先花面值大的，能大的就一直大的，只要不超过c,然后再能小的就一直小的，补全没超过但是又不够那一部分，这个想法一开始就是对的，只不过我写的时候是排序，然后从前往后取，不能取了再从后往前取。。。这样一直wa，后来无奈了 我看了下题解，卧槽，没错啊（这最蛋疼了，因为我敲题的错误思路和正确思路没冲突，说不清..）结果就一直以为自己姿势不对，然后不停的重新敲，优化优化优化。。还是wa，最后无奈了，直接找了个代码看看，结果...哎！  说下正解吧、

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。