HAOI 2013 花卉节
题目描述：
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 人满意
输入格式 Input Format
第1行: N B
第2..N+1行: Pi Ci （i=1，2，....，N）。
输出格式 Output Format
一个整数，最多可以让多少市民满意
样例输入 Sample Input
5 50
5 3
1 1
10 4
7 2
60 1
样例输出 SampleOutput
8
时间限制 Time Limitation
1s
来源 Source
haoi2013
其实就是一道很简单的贪心题目 大部分人可能会问这不是背包DP么，为什么贪心是正确的呢
首先我们知道背包肯定做不了 我们考虑对于两朵不同种花，选择其中的一朵对答案的贡献都是1
那么我们为什不选择花费少的那朵那，这就是贪心为什么是对的（因为对答案的贡献都为1，背包dp不能用是因为对答案的贡献不同且不能分割）
这道题直接用乘法可能会爆long long
我们把乘法转化为乘法即可
ans表示还剩多少钱，sum表示满足多少人,比如现在排完序后枚举到第i个物品的时候
ll k=ans/e[i].v;
if(k==0) break;
sum+=min(e[i].w,k);
ans-=min(e[i].w,k)*e[i].v;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline ll read(){
ll x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=1e6+10;
ll sum;
struct node{
ll v,w;
}e[MAXN];
inline bool mycmp(node n,node m){
return n.v<m.v;
}
int main(){
ll n=read();ll ans=read();
for(int i=1;i<=n;i++){
e[i].v=read();e[i].w=read();
}
sort(e+1,e+n+1,mycmp);
for(int i=1;i<=n;i++){
ll k=ans/e[i].v;
cout<<k<<endl;
if(k==0) break;
sum+=min(k,e[i].w);
ans-=min(k,e[i].w)*e[i].v;
}
cout<<sum<<endl;
return 0;
}
相关知识
【南京桂花节】2013南京桂花节开幕式—时间—地点—门票
2013焦作红叶节即将开幕
2013武汉大学樱花节时间门票观赏指南
2013北京玉渊潭樱花节几号(时间门票地址全攻略)
【2013上海花卉园艺展会】
2013玉渊潭樱花节全攻略
与鲜花约会?香港2013花卉展览
实拍2013北京玉渊潭樱花节
2013上海花卉园艺展览会
2013颐和园桂花节时间门票及交通
网址: HAOI 2013 花卉节 https://m.huajiangbk.com/newsview2153769.html
| 上一篇: 南头街道荷兰花卉小镇首届花漾生活 |
下一篇: 深圳清明节带女朋友去哪里玩 |
