【HAOI1529】花卉节

HA果然是弱省中的弱省……

原题：

ZZ市准备在绿博园举办一次花卉节。Dr.Kong接受到一个任务，要买一批花卉进行布置园林。
能投入买花卉的资金只有B元 (1 <= B <= 10^18) 。Dr.Kong决定做一个社会调查，统计一下市民们都喜欢哪种花卉，以便在有限的资金范围内，让更多的市民都能找到并标注一盆自己喜欢的花卉（一盆花只能一位市民标注）。  
经调查统计，市场上有N (1 <= N<=100,000)种不同类型的花卉，第i种花卉的价格是Pi(1 <= Pi <= 10^18) 。有Ci (1 <= Ci <= 10^18) 个市民喜欢。
你能帮助Dr.Kong计算一下，在不透支的情况下，如何购买花卉才能让更多的市民都能找到并标注一盆自己喜欢的花卉？  
例如：Dr.Kong 有 50块钱，有5种不同类型的花卉：

　　   花卉类型　　　　   价格/盆　　　　  喜欢该类型花卉市民的人数　　　　  
　　　　  1　　　　　　　　   5　　　　　　　　　　  3
　　　　  2　　　　　　　　   1　　　　　　　　　　  1
　　　　  3　　　　　　　　  10　　　　　　　　　　  4
　　　　  4　　　　　　　　   7　　　　　　　　　　  2
　　　　  5　　　　　　　　  60　　　　　　　　　　  1

显然，Dr.Kong不能购买第5种类型的花卉,因为他不够钱。
下面的购买方案是最优的：
　　第1种花卉买3盆；第2种花卉买1盆；第3种花卉买2盆；第4种花卉买2盆。
 总共花费：5*3+1*1+10*2+7*2=50，这样，Dr.Kong 最多能让3+1+2+2 =8 人满意。

贪心：如果有一盆比较贵的花和一盆不是很贵的花，如果剩下的钱能买贵的花的话也一定能买更多不是很贵的花

所以按照价格排序，从小到大把能买的全买了就行，注意longlong

没了

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 long long read(){long long z=0,mark=1;  char ch=getchar();
 8     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1;  ch=getchar();}
 9     while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘;  ch=getchar();}
10     return z*mark;
11 }
12 struct dcd{long long x,y;}a[110000];
13 long long n,m;
14 bool compare(dcd x,dcd y){return x.x<y.x;}
15 int main(){//freopen("ddd.in","r",stdin);
16     cin>>n>>m;
17     for(int i=1;i<=n;i++)  a[i].x=read(),a[i].y=read();
18     sort(a+1,a+n+1,compare);
19     long long ans=0;
20     for(int i=1;i<=n;i++)  ans+=min(m/a[i].x,a[i].y),m-=min(m/a[i].x,a[i].y)*a[i].x;
21     cout<<ans<<endl;
22     return 0;
23 }

View Code

【HAOI1529】花卉节

原文：http://www.cnblogs.com/JSL2018/p/6337581.html