公交车问题一男子于12:00来到一个公交车站,他记录下了12:00-12:59所有公交车的到站情况。现在我们假设:
    1) 同一条线路的公交车到站是有规律的,也就是每隔一个固定时间就会有一辆车到站。
    2) 公交车的到站是以分钟为最小计量单位的。
    3) 每一条线路的车至少到站两次。
    4) 经过该车站的公交车线路≤17条。
    5) 不同线路的公交车可以同时到达该车站。
    6) 不同线路的公交车到该车站的时刻和时间间隔均可以相同。
现在问,根据该男子的记录,最少有多少条公交车线路经过该车站?
 

 


[分析]
此题是明显的搜索题,且DFS较为合适。由于每条线路只需要第一和第二辆车到达的时刻,就可以完全确定,因此我们可以依次考虑12:00-12:59的车辆到达情况。假设某一个时刻有一辆车到达本站,那么它有两种可能:
1) 它是一条新线路的第一辆车;2) 它是已有某条线路的第二辆车。
如果是情况1),那么我们需将它作一下标记。如果是情况2),那么我们就枚举该线路的第一辆车在何时刻到达,有了此时刻,那么就可以完全确定这条线路,随后我们可以把这一条线路从记录中删除。再根据题干中提到的那么约束条件,我们就可以写出程序了。

发表评论

电子邮件地址不会被公开。

Post Navigation