| 题目名称 | 3493. [POJ 1167]公交线路 2 |
|---|---|
| 输入输出 | buses.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 6 |
| 题目来源 |
 gao
于2020-10-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：10， 通过率：10% | ||||
 Eddy2008 |
100 | 0.005 s | 0.96 MiB | C++ |
|
Eddy2008 |
83 | 1.008 s | 1.91 MiB | C++ |
|
Eddy2008 |
83 | 1.032 s | 1.91 MiB | C++ |
|
Eddy2008 |
83 | 1.036 s | 1.91 MiB | C++ |
|
Eddy2008 |
66 | 2.030 s | 2.87 MiB | C++ |
|
Eddy2008 |
50 | 2.144 s | 2.87 MiB | C++ |
|
Eddy2008 |
33 | 1.091 s | 1.91 MiB | C++ |
|
Eddy2008 |
33 | 4.280 s | 4.78 MiB | C++ |
|
Eddy2008 |
16 | 5.000 s | 4.78 MiB | C++ |
|
Eddy2008 |
16 | 5.000 s | 4.78 MiB | C++ |
| 关于 公交线路 2 的近10条评论(全部评论) |
|---|
【题目描述】
一个人12点到达公共汽车站。他在12:00-12:59（一个小时）呆在那里。他记下每辆公共汽车到达的时间。
每条公交线路至少停靠2次。
测试示例中的公交线路数量应<=17。
不同路线的公共汽车可以同时到达。
多条公交线路可以具有相同的首次到达时间和/或时间间隔。
如果两条公交线路的发车时间和间隔相同，则它们是不同的，并且都要呈现出来。
求满足公交时间表的最少的公交线路。
【输入格式】
输入包含一个数字n（n<=300），表示已经记录了多少到达的公共汽车，然后是按升序排列的到达时间。
【输出格式】
输出包含一个整数，表示最少的公交线路。
【样例输入】
17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
【样例输出】
3
【来源】
《算法竞赛进阶指南》POJ1167 IOI 1994