前言

  谈到生活中经常坐的公交车，比较常见的算法问题可能是寻找“耗时最少公交路线”、“最少换乘公交路线”、“最便宜公交路线”、“综合最优公交路线”等。这些算法由于在地图软件中经常被使用，已经被大家研究得非常透彻，比如 Dijkstra 算法就可以用来计算“最短距离公交路线”。如想了解更多，可以阅读参考资料 2 给出的中文文献。

  相比这些常见的算法问题，不如让我们来一起看看不大被人提及的“公交计费问题”。笔者经常在下雨的时候乘坐公交车，每次上车前会先取一张票，然后下车前可以看屏幕显示来知道票价。于是笔者就有了一个小问题：票价是如何正确显示的，是否可以对其建模并写个小程序模拟一下。

问题描述

  如图 1 所示为公交计费问题描述。

• (a) 公交路线图（图中为右循环路线，但对应的左循环路线也存在），0~20 为站点编号，且 1~3 与 20~18 分别对应相同。公交从站点 0 出发，按照箭头所指的方向依次行进，最终回到站点 0 并停止运行。
• (b) 相邻站点间距离，以 km 为距离计算单位，给出的数值为公交在站点间实际行进距离。
• (c) 公交票价计算方式，距离不足 2 km 为基本票价 190 日元，超过 2 km 的话每超过 1 km 加收 50 日元，如不足 1 km 按照 1 km 计算。注意，此处的距离为循环线路中上车站点与下车站点的有效距离，即站点间在循环线路上的最短距离而非实际运行距离。比如，即使从站点 0 上车，经过一圈循环后再从站点 0 下车，也只能收取基本票价 190 日元，因为有效距离为 0 km。（以上计算方式参考自资料 3）
• (d) 公交最后返回起始站点时计费状态，灰底色为站点编号，白底色为票价。

问题目标

1. 打印欢迎消息，提示是否从站点 0 发车；
2. 发车后，通过回车或其他操作在下一站点停车，打印当前票价状态，尚未抵达站点票价为空；
3. 经过循环后回到站点 0，通过回车或其他操作停车，打印当前票价状态，如图 1(d) 所示。

解决方案

问题分析

  解决公交计费问题，首先要将图 1 中给出的信息进行集成，可得如下图 2。其中，站点间的橙色数字为相邻站点间距离，红色数字为几个关键（0~2 km，2~3 km 和 3~4 km 的阈值站点）站点与出发站点 0 之间的有效距离。

  其实整个问题的核心就在于对有效距离的理解。从题干可知，有效距离并非是实际行进距离。这主要是因为给出的公交路线是环线而非直线，即出发站点与结束站点为同一站点。除此之外，刚开始的 1~3 与最后的 20~18 三个站点是重合的。根据给出的例子解释，我们可以将这里的“有效距离”粗略定义为“上车站点与下车站点在公交路线上正反距离的最小值”。我们不妨从以下示例中进一步加深对于“有效距离”的理解：（~ 表示“大约”）

• 例 1：上车站点为站点 3，下车站点为站点 17。因为站点 3 与站点 18 重合，所以有效距离等同于站点 17 和 18 之间的距离 0.45 km。
• 例 2：上车站点为站点 5，下车站点为站点 18。如例 1 方式计算可得有效距离为 0.85 km。
• 例 3：上车站点为站点 4，下车站点为站点 17。虽然按照路线实际行进距离很远，但是实际两站之间路线上最短距离大约为 0.45 km，即有效距离为 ~0.45 km。
• 例 4：上车站点为站点 5，下车站点为站点 15。如例 2 方式计算可得有效距离为 ~1.6 km。
• 例 5：上车站点为站点 6，下车站点为站点 14。按照图中方向实际行进距离计算，可知正向距离为 2.75 km，按照路线上最短反向距离为 ~2.25 km，因此有效距离为 ~2.25 km。

得出总结：

• 从例 1、2 可以看出，当上车站点和下车站点分别在重合直线和循环圈上时，位于重合直线上的站点需要注意切换到对应站点进行双重计算正反向距离，从而得到正确的有效距离。
• 从例 3~5 可以看出，当上车站点和下车站点均在循环圈上时，计算反向距离不涉及直线站点（即跨过出发站点 0）。即使站点 17 到站点 4 的实际行进路线不存在，也需以站点 17 到站点 4 闭合的循环圈来进行计算反向距离。

算法描述

变量声明

变量名	变量类型	描述
distances	list	站点列表，[0, 0.2, 0.3, …]
currentStop	int... 剩余内容已隐藏 查看完整文章以阅读更多 查看完整文章