| 题目名称 | 1508. [CTSC 2000]公路巡逻 |
|---|---|
| 输入输出 | patrol.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-01-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：7， 通过率：71.43% | ||||
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.876 s | 33.44 MiB | C++ |
|
瑆の時間~無盡輪迴·林蔭 |
100 | 0.892 s | 33.44 MiB | C++ |
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.996 s | 102.51 MiB | C++ |
 cstdio |
100 | 1.001 s | 20.09 MiB | C++ |
|
mikumikumi |
100 | 1.032 s | 102.51 MiB | C++ |
|
瑆の時間~無盡輪迴·林蔭 |
70 | 0.849 s | 33.44 MiB | C++ |
|
mikumikumi |
40 | 4.144 s | 14.06 MiB | C++ |
| 关于 公路巡逻 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
由于评测姬的速度变慢，所以改了时限
| ||||
|
由于数据淼……所以本题最重要的优化有两个：
①无穷大的状态不判断 ②取到0直接退出 还有，“同时出发”不算相遇，但是！“同时出发同时到达”算相遇 坑爹呢这是…… | ||||
【题目描述】
在一条没有分岔的高速公路上有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