P5159: 糖果-训练套题T4T2
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
2. 糖果 [cbuying.pas/ c/cpp]
【问题描述】
有
N(1≤
N~<100,000)种不同类型的糖果，每种糖果数量无限多。第
i种糖果每颗的价格是
P_i(1≤
P_i≤
10^18)，有
C_i (1≤
C_i≤
10^18)头牛想吃这种糖果。
Farmer John拥有金钱
B元
(1≤
B≤
10^18)给奶牛们买糖果。他最多可以给多少头牛买到糖果
?所有的奶牛都只吃它喜欢的类型的一颗糖果。
例如：
FJ有
50块钱，有
5种不同类型的糖果：
糖果类型
每颗糖果价格
想吃该类型糖果的奶牛数量
1 5 3
2 1 1
3 10 4
4 7 2
5 60 1
显然，
FJ不能购买第
5种类型的糖果，因为他钱不够。
下面的购买方案是最优的：
买
1颗类型
2的糖果。
买
3颗类型
1的糖果。
买
2颗类型
4的糖果。
买
2颗类型
3的糖果。
总共花费
1+3*5+2*7+2*10=50，这样，
FJ最多能满足
1+3+2+2=8头牛的糖果需求。
【输入数据】
第
1行：两个整数：
N，
B。
第
2．．
N+1行：每行两个整数：
P_i，
C_i。
【输出数据】
一行，一个整数，最多可以让多少头奶牛吃到糖果。
【输入样例】
5 50
5 3
1 1
10 4
7 2
60 1
【输出样例】
8
【提示】
cbuying
算法分析：
由于每头奶牛只需要吃一颗糖果，而题目求的是让尽量多的奶牛能吃到糖果，因此，应该尽量购买价格便宜的糖果。先按糖果价格从小到大排序，然后向后扫描，直到用完了金钱或者购买完了所有糖果。时间复杂度：O(NlogN)。