bzoj2014[Usaco2010 Feb]Chocolate Buying*

bzoj2014[Usaco2010 Feb]Chocolate Buying

题意：

n种巧克力，每种有个单价和最多能买几块，问有B块钱一共最多能买几块。n≤100000

题解：

贪心，按单价排序。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll long long
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 100010
 7 using namespace std;
 8 
 9 inline ll read(){
10     char ch=getchar(); ll f=1,x=0;
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
13     return f*x;
14 }
15 int n; ll b,ans;
16 struct nd{ll p,c;}; nd nds[maxn];
17 inline bool cmp(const nd &a,const nd &b){return a.p<b.p;}
18 int main(){
19     n=read(); b=read(); inc(i,1,n)nds[i]=(nd){read(),read()}; sort(nds+1,nds+1+n,cmp);
20     inc(i,1,n){
21         ll use=min(nds[i].c,b/nds[i].p);
22         b-=use*nds[i].p; ans+=use; if(use!=nds[i].c)break;
23     }
24     printf("%lld",ans); return 0;
25 }

20160811