跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#X261108E. 物资装载

物资装载

题目描述

仓库有 NN 堆物资。第 ii 堆的总重量为 mim_i,总价值为 viv_i。运输袋最多能承受 TT 单位重量。

每堆物资都可以 任意分割,取走其中任意比例的一部分,重量和价值按同一比例计算。可以只取一部分物资,也可以不取;总重量不得超过 TT。求最多能装走的总价值。

输入格式

第一行两个整数 N,TN,T。接下来 NN 行,每行两个整数 mi,vim_i,v_i。

输出格式

输出最大总价值,保留两位小数。评测允许与精确最优值不超过 0.0050.005 的绝对误差。

数据范围与计分

1≤N≤1001\le N\le100,1≤T≤10001\le T\le1000,1≤mi,vi≤1001\le m_i,v_i\le100。

  • 基础部分:占总分的 60 分,保证 N=1N=1。
  • 完整部分:另占 40 分,满足上述完整数据范围。
  • 测试点独立计分,正确处理基础部分的全部测试点可获得 60 分;正确处理全部测试点可获得 100 分。

样例 1

1 2
3 10
6.67

样例 2

2 1
100 100
1 99
99.00

样例说明

样例 1 装走这堆物资的三分之二,价值为 20/320/3,输出 6.67。样例 2 可以把第二堆全部装走。

相关

在下列比赛中:

全栈考核