记录编号	132158	评测结果	AAAAAAAAA
题目名称	[USACO Oct09] 零用钱	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.176 s
提交时间	2014-10-25 15:37:11	内存使用	0.40 MiB

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
struct dx
{
        int v;
        int b;
};
bool my_comp(const dx &a,const dx &c)
{
    return a.v>c.v;
}
void init();
dx a[11000];
int fang=0,sheng,n,c,sum=0;
void init()
{
        memset(a,0,sizeof(a));
        cin>>n>>c;
        for(int i=1;i<=n;i++)  cin>>a[i].v>>a[i].b;
        sort(a+1,a+n+1,my_comp);
        for(int i=1;i<=n;i++)
        {
                if(a[i].v>=c)
                {
                        sum+=a[i].b;
                        fang++;
                }
        }
}
int main()
{
	freopen("allow.in","r",stdin);
	freopen("allow.out","w",stdout);
	    init();
        while(sheng<=0)
        {
                sheng=c;
                for(int i=fang+1;i<=n;i++)
                {
                        while(sheng-a[i].v>=0&&a[i].b>0)
                        {
                                sheng-=a[i].v;
                                a[i].b--;
                        }
                }//跳出循环时钱数>=c;
                for(int i=n;i>=fang+1;i--)
                {
                        while(sheng>0&&a[i].b>0)
                        {
                                sheng-=a[i].v;
                                a[i].b--;
                        }
                }//再用小面额填充剩下的空；
                if(sheng<=0)
                sum++;
        }
        cout<<sum;
        return 0;
}