#P1018. Communication System

    ID: 19 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>贪心Tehran 2002First Iran Nationwide Internet Programming Contest

Communication System

描述
我们收到了来自 Pizoor Communications Inc. 的一个特殊通信系统的订单。该系统由多个设备组成。对于每个设备,我们可以从多个制造商中选择。来自不同制造商的相同设备在最大带宽和价格上有所不同。

整体带宽(B)是指通信系统中所有选定设备的最小带宽,总价格(P)是所有选定设备价格的总和。我们的目标是为每个设备选择一个制造商,以最大化 B/PB/P

输入
输入文件的第一行包含一个整数 t1t10t(1 ≤ t ≤ 10),表示测试用例的数量,随后是每个测试用例的输入数据。每个测试用例的第一行包含一个整数 n1n100n(1 ≤ n ≤ 100),表示通信系统中设备的数量,接下来是 nn 行,格式如下:第 ii1in(1 ≤ i ≤ n)mi1mi100m_i(1 ≤ m_i ≤ 100)开头,表示第 ii 个设备的制造商数量,随后是 mim_i 对正整数,每对分别表示该制造商提供的设备的带宽和价格。

输出
对于每个测试用例,您的程序应输出一行,包含一个数字,表示该测试用例中可能的最大 B/PB/P。将输出中的数字四舍五入到小数点后 33 位。


示例
假设输入如下:

1
3
3 100 25 150 35 80 20
2 120 30 60 20
2 100 25 50 15

输出应为:

0.533

解释

  • 对于第一个设备,选择带宽 80、价格 20 的制造商。
  • 对于第二个设备,选择带宽 120、价格 30 的制造商。
  • 对于第三个设备,选择带宽 100、价格 25 的制造商。

整体带宽 B=min(80,120,100)=80 B = \min(80, 120, 100) = 80 ,总价格 $ P = 20 + 30 + 25 = 75 。因此,。 因此, B/P = 80/75 \approx 1.0667 $,但根据示例输出,可能需要进一步调整选择。