当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

4128:Running relay

题目描述
The school track-and-field team is taking a running relay race. There are n (2<=n<=104) members in the team. In order to let everybody participate in the race, each member should run at least d (0<=d<=10) meters. Besides that, everyone can run arbitrary distance. The whole length of the track is L (1<=L<=105) meters.

For the ith member in the team, if he is in a good mood, then it takes him ti seconds (1<=ti<=4×104) to run one meter. If he is in a bad mood, then it takes him si (1<=si<=4×104, 1<=ti<=si) seconds to run one meter.

As the coach of the team, you can assign the running distance of each member in advance. Suppose that, it takes S seconds for the team to complete the relay race if all the members are in bad moods and it takes T seconds for the team to complete the relay race if all the members are in good moods. You do want to have a good score. But you don’t want to have a very bad score even if someone is in a bad mood. So you want to know the minimum value of T on condition that S should not be larger than W (1<=W<=2147483647).
输入解释
The input begins with a line containing an integer, indicating the number of test cases. There are no more than 100 test cases.

For each case, the first line begins with four integers --- the above mentioned n, d, L and W. Then n lines follow, each representing a member. Each line contains two integers s and t, meaning that the member spends s seconds to run one meter when he/she is in a bad mood, and spends t seconds to run one meter when he/she is in a good mood.
输出解释
For each test case, if you cannot find a proper way to assign the running distance of each member, output a string “No solution” in a line. Otherwise, output the minimum value of T (rounded to 2 digits after the decimal point) in a line.
输入样例
2
2 1 20 141
8 3
6 6
3 8 20 200
8 3
6 6
7 1
输出样例
88.50
No solution
提示
In the first case, the first member runs 10.5 meters and the second member runs 9.5 meters. S=8×10.5+6×9.5=141=W, T=3×10.5+6×9.5=88.5.

In the second case, every member should run at least 8 meters. But the length of the track is only 20 meters. Because 8×3>20, there is no solution.
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-4128

最后修改于 2020-10-25T23:10:32+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/2000MS(Java/Others) 32768/32768K(Java/Others)