题目大意：农夫和牛又搞新花样了，现在农夫想给Bessie每个星期都给一点零用钱，农夫有一堆面值的钱币，并且这个钱币都能被上一个钱币整除（1,5,10,50），并且钱币有一定数量，要你求最多可以给多少个星期超过C的零用钱？
这一题如果没有可以被整除的条件，那只能用动态规划了，但是这一题给了这个条件，那就说明，我们的组合都是满足单一原则的（比如单次组合最接近c的组合总是从大到小，再从小到大排列面额数，而没有其他组合），也就是可以贪婪算法。
这个贪婪算法可以分成三个步骤：
S1：如果钱币的面值大于C，那就直接一个一个星期分
S2：如果钱币的面值小于C，那么我们就从大到小排列钱币，直到大于大于等于C为止
S3：如果S2以后，钱币数任然达不到要求，那么我们就从小到大排列从新再找，直到大于C为止
如果S4以后，还是不能找到大于C的组合，那么直接退出即可
这样的贪婪的原理是因为，我们的硬币总是等效的，因为他在达到C可以分发的情况下只是数量的区别，所以我们想尽量让我们的组合数靠近C。
其他东西在代码的注释上应该写的很清楚噜
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; typedef struct money
{
int value;
int numbers;
}Coin_Set;
int fcomp(const void *a, const void *b)
{
return (int)((*(Coin_Set *)b).value - (*(Coin_Set *)a).value);
} static Coin_Set coins[];
static int used[]; void Search(const int, const int); int main(void)
{
int n, least_V; while (~scanf("%d%d", &n, &least_V))
{
for (int i = ; i < n; i++)
scanf("%d%d", &coins[i].value, &coins[i].numbers); qsort(coins, n, sizeof(Coin_Set), fcomp);//先按照面值排序(从大到小)
Search(n, least_V);
} return ;
} void Search(const int n, const int least_V)
{
int ans = , i, pos, j, min_ans_tmp, used_tmp, last; //Step1:如果比least_v大，直接加入ans中
for (i = ; i < n && coins[i].value >= least_V; i++)
{
ans += coins[i].numbers;
coins[i].numbers = ;
}
for (pos = i;;)
{
memset(used, , sizeof(used));
//Step2:尽量凑到least_V之前
last = least_V;
for (j = pos; j < n; j++)
{
used_tmp = min(last / coins[j].value, coins[j].numbers);//先设定好一个last要分到多少枚j硬币 //注意，上一步如果last<coins[j].value的时候，返回为0，下面相当于不更新last和used
last -= coins[j].value * used_tmp;
used[j] = used_tmp;
}
//Step3:从后往前，凑到比least_V大为止
for (j = n - ; j >= && last > ; j--)
{
used_tmp = (last + coins[j].value - ) / coins[j].value;
used_tmp = min(used_tmp, coins[j].numbers - used[j]);//上一个循环用掉了一些哦，一定要注意 //上同
last -= coins[j].value*used_tmp;
used[j] += used_tmp;//注意是“+=”，因为会重复
}
if (last > ) break;//凑不齐，直接退出 min_ans_tmp = INT_MAX;
for (j = pos; j < n; j++)//找到可以完全分配到的最大星期数
{
if (!used[j]) continue;
if (coins[j].numbers / used[j] < min_ans_tmp)
min_ans_tmp = coins[j].numbers / used[j];
}
for (j = pos; j < n; j++)
{
if (!used[j]) continue;
coins[j].numbers -= min_ans_tmp*used[j];
}
ans += min_ans_tmp;
}
printf("%d\n", ans);
}
