题目大意：农夫和牛又搞新花样了，现在农夫想给Bessie每个星期都给一点零用钱，农夫有一堆面值的钱币，并且这个钱币都能被上一个钱币整除（1,5,10,50），并且钱币有一定数量，要你求最多可以给多少个星期超过C的零用钱？
这一题如果没有可以被整除的条件，那只能用动态规划了，但是这一题给了这个条件，那就说明，我们的组合都是满足单一原则的（比如单次组合最接近c的组合总是从大到小，再从小到大排列面额数，而没有其他组合），也就是可以贪婪算法。
这个贪婪算法可以分成三个步骤：
S1：如果钱币的面值大于C，那就直接一个一个星期分
S2：如果钱币的面值小于C，那么我们就从大到小排列钱币，直到大于大于等于C为止
S3：如果S2以后，钱币数任然达不到要求，那么我们就从小到大排列从新再找，直到大于C为止
如果S4以后，还是不能找到大于C的组合，那么直接退出即可
这样的贪婪的原理是因为，我们的硬币总是等效的，因为他在达到C可以分发的情况下只是数量的区别，所以我们想尽量让我们的组合数靠近C。
其他东西在代码的注释上应该写的很清楚噜
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 typedef struct money 8 { 9 int value; 10 int numbers; 11 }Coin_Set; 12 int fcomp(const void *a, const void *b) 13 { 14 return (int)((*(Coin_Set *)b).value - (*(Coin_Set *)a).value); 15 } 16 17 static Coin_Set coins[20]; 18 static int used[20]; 19 20 void Search(const int, const int); 21 22 int main(void) 23 { 24 int n, least_V; 25 26 while (~scanf("%d%d", &n, &least_V)) 27 { 28 for (int i = 0; i < n; i++) 29 scanf("%d%d", &coins[i].value, &coins[i].numbers); 30 31 qsort(coins, n, sizeof(Coin_Set), fcomp);//先按照面值排序(从大到小) 32 Search(n, least_V); 33 } 34 35 return 0; 36 } 37 38 void Search(const int n, const int least_V) 39 { 40 int ans = 0, i, pos, j, min_ans_tmp, used_tmp, last; 41 42 //Step1:如果比least_v大，直接加入ans中 43 for (i = 0; i < n && coins[i].value >= least_V; i++) 44 { 45 ans += coins[i].numbers; 46 coins[i].numbers = 0; 47 } 48 for (pos = i;;) 49 { 50 memset(used, 0, sizeof(used)); 51 //Step2:尽量凑到least_V之前 52 last = least_V; 53 for (j = pos; j < n; j++) 54 { 55 used_tmp = min(last / coins[j].value, coins[j].numbers);//先设定好一个last要分到多少枚j硬币 56 57 //注意，上一步如果last<coins[j].value的时候，返回为0，下面相当于不更新last和used 58 last -= coins[j].value * used_tmp; 59 used[j] = used_tmp; 60 } 61 //Step3:从后往前，凑到比least_V大为止 62 for (j = n - 1; j >= 0 && last > 0; j--) 63 { 64 used_tmp = (last + coins[j].value - 1) / coins[j].value; 65 used_tmp = min(used_tmp, coins[j].numbers - used[j]);//上一个循环用掉了一些哦，一定要注意 66 67 //上同 68 last -= coins[j].value*used_tmp; 69 used[j] += used_tmp;//注意是“+=”，因为会重复 70 } 71 if (last > 0) break;//凑不齐，直接退出 72 73 min_ans_tmp = INT_MAX; 74 for (j = pos; j < n; j++)//找到可以完全分配到的最大星期数 75 { 76 if (!used[j]) continue; 77 if (coins[j].numbers / used[j] < min_ans_tmp) 78 min_ans_tmp = coins[j].numbers / used[j]; 79 } 80 for (j = pos; j < n; j++) 81 { 82 if (!used[j]) continue; 83 coins[j].numbers -= min_ans_tmp*used[j]; 84 } 85 ans += min_ans_tmp; 86 } 87 printf("%d ", ans); 88 }
