问题 5320 --糖果-训练套题T4T2

5320: 糖果-训练套题T4T2

时间限制: 1 Sec  内存限制: 128 MB
提交: 44  解决: 8
[提交][状态][讨论版][命题人:]

题目描述

2. 糖果 [cbuying.pas/ c/cpp]

【问题描述】

N(1N~<100,000)种不同类型的糖果,每种糖果数量无限多。第i种糖果每颗的价格是P_i(1P_i10^18),有C_i (1C_i10^18)头牛想吃这种糖果。

    Farmer John拥有金钱B(1B10^18)给奶牛们买糖果。他最多可以给多少头牛买到糖果?所有的奶牛都只吃它喜欢的类型的一颗糖果。

  例如:FJ50块钱,有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行:两个整数:NB

   2..N+1行:每行两个整数:P_iC_i

【输出数据】

一行,一个整数,最多可以让多少头奶牛吃到糖果。

【输入样例】

    5  50

    5  3

    1  1

    10 4

    7  2

    60 1

【输出样例】

8

提示


cbuying



  算法分析:



  由于每头奶牛只需要吃一颗糖果,而题目求的是让尽量多的奶牛能吃到糖果,因此,应该尽量购买价格便宜的糖果。先按糖果价格从小到大排序,然后向后扫描,直到用完了金钱或者购买完了所有糖果。时间复杂度:O(NlogN)

来源

 

[提交][状态]