/ Vijos / 题库 /

月球金属

月球金属

时间限制:1秒  内存限制:256M


【题目描述】

  某天小H利用神州飞船飞到了月球上,上面有许多珍贵的金属,小H虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。

  但是他只带着一个口袋,口袋至多只能装重量为 \(w\) 的物品。月球上金属有 \(n\) 个种类, 每种金属重量不同,分别为 \(v_1, v_2, … , v_n\),同时每个种类的金属总的价值也不同,分别为 \(p_1, p_2, …, p_n\)。小H想一次带走价值尽可能多的金属,问他最多能带走价值多少的金属?

  注意到金属是可以被任意分割的,并且金属的价值和其重量成正比。

【输入格式】

  第1行是有两个正整数 \(n,w\),\(n\) 表示金属种类,\(w\) 表示口袋承重上限。
  接下来的 \(n\) 行,每行包含两个整数,分别表示一种金属的重量 \(v_i\) 和价值 \(p_i\)。

【输出格式】

  输出最大价值,精确到小数点后 2 位。

【输入输出样例】

 Input

5 10000 
1 43
43 323
35 45
43 54
87 43

 Output

508.00

【数据限制】

  对于 \(100\%\) 的数据,\(0<n<=50000\),\(0<C,v_i,p_i<=10^9\)。

【来源】

  Mr.he

信息

ID
1753
难度
(无)
分类
贪心 | 其他 | 排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
4
上传者