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

建议使用的浏览器:

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

1919:Ship Journey

题目描述
Background
Captain Hansen wants to navigate with his little barge from Hamburg downstream to Cuxhaven on the river Elbe. During this journey he must take the tide into account. When the tide is falling the water flows to the North Sea and speeds up the ship. When the tide is rising the drift of the tide reduces the real speed. The drift is not constant, but varies over the time. Captain Hansen now wants to know, when to start in order to minimize the time for the journey.
Of course, there are deadlines to meet and Hansen runs a "just in time" service, so the arrival should be as late as possible, but not after a given deadline.
The Problem
Create a program which calculates the optimal time t of departure. The optimal time depends on two criteria:
1. Departing at t guarantees that Hansen will reach Cuxhaven before a given deadline (i.e., arrival time < deadline).
2. For departure time t, the time for the journey is minimal.
3. If multiple such departure times exist, Hansen picks the latest one that will bring him to Cuxhaven The distance between Hamburg and Cuxhaven is 100 km. The ship moves with a constant speed of 10 km/h through water (without drift!). The real speed (speed over ground) is calculated by adding or subtracting the drift speed. The drift has the same speed and direction on the whole river at any time. Speed and direction change not more than once per minute and remain constant until the next change.
输入解释
The first line contains the number of scenarios.
For each scenario, you find the time d of latest possible arrival. For your convenience, this time is given in minutes starting from midnight (300 <= d <= 1440). Then the number d of data sets containing drift data is given (1 <= d <= 100). A drift data set has the form "m s" where m and s are integers. Value m specifies the minute from which the given speed and direction hold and s gives the new tide speed and direction (0 <= m <= 10000, -10 <= s <= 10). Positive values of s stand for drift from Hamburg to Cuxhaven, negative values specify drift in the opposite direction.
Time values are given in minutes only, speed in km/h, distances in km. You may assume that a solution exists and that the data set begins with an entry for time 0 specifying the initial drift speed at starting time.
输出解释
For each scenario print a single line containing the optimal time time of departure.
You may assume that a solution exists on that particular day, i.e., the latest arrival time can be met when starting at midnight of that day.
输入样例
1
900
4
0 -3
60 0
90 2
150 4
输出样例
471

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-1919

最后修改于 2020-10-29T06:17:50+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536