http://poj.org/problem?id=3040
FJ 有n种不同面值的硬币，每种硬币都有相应的个数，大面值的硬币值总能被小面值的硬币值整除，每周需要支付 Bessie c元，问最多能支付Bessie多少周。
这题之所以能贪心，据说关键是这句话 where each denomination of coin evenly divides the next-larger denomination。
如果没有这个限制条件，有些情况是取不到最优解的。
把面值从小到大排序，然后从尾到头开始扫，能给多少就给多少，如果面值不够，就从头到尾扫，尽量取刚好超过数额的。
参考了别人代码，感觉写的很精妙。自己的水平还很欠缺。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue> #define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 1000000000
#define N 100010
using namespace std; pair<int,int>p[];
int use[];
int main()
{
int n,c,sum;
scanf("%d%d",&n,&c);
sum=;
for(int i=;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
sort(p,p+n);
for(int i=;i<n;i++) //从大面值 开始 如果面值 大于c 那么直接累加。
if(p[i].first>=c)
{
sum+=p[i].second;
p[i].second=;
}
while(true) //不断循环，直到不能在支付为止。
{
int tmp=c;
int flag=;
memset(use,,sizeof(use)); //记录每个面值的硬币使用了多少。
for(int i=n-;i>=;i--) //从大面值开始扫。
{ //注意这里只有一次循环，就把所有面值的使用情况扫出来了，因为如果不能用当前面值支付的话 k会变成0，并且要么会刚好支付完，要么tmp>0
if(p[i].second) //当前面值还有 不会出现浪费当前面值的情况
{
int k=tmp/p[i].first; //为了支付c元 当前面值最多可以用多少个，
int mi=min(k,p[i].second); //取最小值
tmp-=p[i].first*mi; //剩下 这么多
use[i]=mi; //记录使用数量
if(tmp<=) {flag=;break;} //tmp小于0 那么本次支付已结束
}
}
if(tmp>) //否则从小到大开始 给
{
for(int i=;i<n;i++)
{
if(p[i].second>use[i]) //如果没使用完
{
while(use[i]<p[i].second) //一直使用，因为当前用的面值是最小的那么这样也是最优的。
{
tmp-=p[i].first;
use[i]++;
if(tmp<=) {flag=;break;}
}
if(tmp<=&&flag==) break; //只有 flag==1的时候 tmp<=0
}
}
}
if(!flag) break; //已经不能完成支付
int mx=maxn;
for(int i=n-;i>=;i--) if(use[i]) mx=min(p[i].second/use[i],mx); //use[i]是一次支付时当前面值使用的情况，那么p[i].second/use[i] 就表示可以支付 这么多次，并且取的是所有当中的最小值。
sum+=mx;
for(int i=n-;i>=;i--) if(use[i]) p[i].second-=mx*use[i]; //取用了 mx次，所以相应数量减少这么多，这样会节省很多时间，不用每次重复计算，是一次很大的优化
}
printf("%d\n",sum);
return ;
}