#P1018. Communication System
Communication System
描述
我们收到了来自 Pizoor Communications Inc. 的一个特殊通信系统的订单。该系统由多个设备组成。对于每个设备,我们可以从多个制造商中选择。来自不同制造商的相同设备在最大带宽和价格上有所不同。
整体带宽(B)是指通信系统中所有选定设备的最小带宽,总价格(P)是所有选定设备价格的总和。我们的目标是为每个设备选择一个制造商,以最大化 。
输入
输入文件的第一行包含一个整数 ,表示测试用例的数量,随后是每个测试用例的输入数据。每个测试用例的第一行包含一个整数 ,表示通信系统中设备的数量,接下来是 行,格式如下:第 行以 开头,表示第 个设备的制造商数量,随后是 对正整数,每对分别表示该制造商提供的设备的带宽和价格。
输出
对于每个测试用例,您的程序应输出一行,包含一个数字,表示该测试用例中可能的最大 。将输出中的数字四舍五入到小数点后 位。
示例
假设输入如下:
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 的制造商。
整体带宽 ,总价格 $ P = 20 + 30 + 25 = 75 B/P = 80/75 \approx 1.0667 $,但根据示例输出,可能需要进一步调整选择。