題意：
? ? ? 有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给奶牛发工资的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。