问题1476--最高得分-2011

1476: 最高得分-2011

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

题目描述

三次方求和的问题,被卡卡西迎刃而解,芭比阿姨拿出钥匙,打开了她后花园的大门。卡
卡西被眼前的景色惊呆了!她从未见过这么多珍奇的鲜花,还有她梦寐以求的在阳光下发出异
样光彩的水晶珠,她慢慢向前走着,忽然被一小块花圃吸引住了。这块花圃中,满是各式各样
闪闪发亮的字母水晶珠,卡卡西心想要是能从这花圃中取出自己想要的字母水晶珠串成项链,
那该多好啊!卡卡西往右手边一看,有一个告示牌,上面写道:亲爱的朋友,如果你想从花圃
中获取字母水晶珠,必须先完成如下游戏:假设所有的字母水晶珠都可以采,每种字母水晶珠
的单颗价值都是一样的,且采摘任意一颗水晶珠所需要的时间都是 1 秒,但是采摘水晶珠的总
时间是有限的,那么应该如何选择自己所要的字母水晶珠,使得总价值最高呢?假设每种字母
水晶珠的数量和总价值用(A,B)表示,其中 A 表示这种水晶珠总的数量,B 表示所有这种水
晶珠的总价值。例如一共有 3 种字母水晶珠,其数量和价值分别如下:(4,20)、(4,24)、(5,
38),留给卡卡西采摘水晶珠的总时间是 10 秒,则选择后两种水晶珠全部摘取,第一种摘取
一颗时,可得摘取的最大价值为 67.00,如果选择摘前两种水晶珠和两颗第三种水晶珠,所能
得价值为 59.20。小朋友,你能帮助卡卡西计算出给定时间内所能采摘水晶珠的最大价值,从
而让她顺利进入花圃采摘字母水晶珠吗?

输入

 共 N+1 行,第一行为两个整数 N(100≤ N≤ 10000)和 T(1≤ T≤ 10000)(中间用
空格隔开),分别表示字母水晶珠种类数和总的采摘时间;后面 N 行中,每行两个整数
S(1≤ S≤ 100)和 V(1≤ V≤ 100)(中间用空格隔开),分别表示这种字母水晶珠的
总数量和总价值。

输出

一行,所能得到的最大价值,输出结果保留两位小数。

样例输入

4 10
3 10 
4 20 
4 24 
5 38

样例输出

67.00

提示

限制:
20%的数据 100≤ N≤ 500 
 60%的数据 100≤ N≤ 999 
100%的数据 100≤ N≤ 10000


cout<<fixed<<setprecision(2)<<123.456<<endl;//输出2位小数

来源/分类


[提交] [状态]