4844：公路巡逻

题目描述

　　　在一条没有分岔的高速公路上有n个关口，相邻两个关口之间的距离都是10km。所有车辆在这条高速公路上的最低速度为60km/h，最高速度为120km/h，并且只能在关口处改变速度。
　　　巡逻的方式是在某个时刻Ti从第ni个关口派出一辆巡逻车匀速驶抵第(ni+1)个关口，路上耗费的时间为ti秒。
两辆车相遇是指它们之间发生超车或者两车同时到达某关口（同时出发不算相遇）。
　　　巡逻部门想知道一辆于6点整从第1个关口出发去第n个关口的车（称为目标车）最少会与多少辆巡逻车相遇，请编程计算之。假设所有车辆到达关口的时刻都是整秒。

输入解释

输入有多组数据。对于每一组数据，第一行为两个用空格隔开的整数，分别为关口数n和巡逻车数m。（1<n<50,1<m<300），接下来的m行每一行为一辆巡逻车的信息（按出发位置递增排序），格式为ni Ti ti，三项用空格隔开，分别表示第i辆巡逻车的出发位置、出发时刻和路上耗费的时间，其中ni和ti为整数，Ti形如hhmmss，表示时、分、秒，采用24小时制，不足两位的数用前置0补齐。（1<=ni<n,05:00:00<=Ti<=23:00:00,300<=ti<=600）

输出解释

　　　对于每一组数据，输出两行：第一行为目标车与巡逻车相遇次数，第二行为目标车与巡逻车相遇次数最少时最早到达第n个关口的时刻（格式同输入中的Ti）。每一组数据之后保留一个空行。

输入样例

3 2
1 060000 301
2 060300 600

输出样例

0
061301

来自杭电HDUOJ的附加信息

Recommend

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

题目来源 CTSC2000

源链接： HDU-4844

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

共提交 0 次

通过率 --%

时间上限	内存上限
20000/10000MS(Java/Others)	65535/32768K(Java/Others)