P3195. 运输时间

解题思路

本题题意虽然容易理解，但是乍一看相当复杂，像小学奥数会学习的那种追及问题。如果真的去计算车辆之间相遇的时间和位置，那会算得非常痛苦。

概念辨析

需要注意本题存在两个概念需要进行辨析：到达时刻和花费时间。

• 到达时刻指的是以某辆车以第0辆车出发为初始时间节点，从0时开始算起的最终到达终点时的时刻。
• 花费时间指的是在某辆车在路上所花的时间。

在本题的语境下，假设已知某辆车的到达时刻为 arrived，它的出发时刻为 i，那么它在路上的花费时间就是 arrived - i。

本题要求我们计算的内容是，最后一辆车的花费时间。所以如果我们能够算出最后一辆车的到达时刻 last_arrived，由于其出发时刻为已知的 N-1，那么就可以直接计算其在路上的花费时间为 last_arrived - (N-1)。

所以本题的重点在于如何计算出最后一辆车的到达时刻。

两辆车的简单情况

辨析了上述两个概念之后，我们先从简单的情况入手分析本题。先考虑两辆车的情况，这是最简单的情况。

假设总路程为 D，A车先出发（0时），速度为 speed_A，B车后出发（1时），速度为 speed_B，考虑两辆车速度的大小关系。若：

• speed_A >= speed_B，即先出发的车是快车，那么晚到的一定是后出发的车，即最后一辆车的到达时刻取决于后出发的慢车，即存在到达时刻为 D / speed_B + 1。其中 1 表示的是晚出发的时间。
• speed_A < speed_B，即后出发的车更快，那么后出发的快车既有可能赶上，也有可能赶不上先出发的慢车。若：
• 后出发的快车赶上了先出发的慢车，由于快车的速度会被降为和慢车一样的速度，之后两车会同时行驶直至终点，最终后车的到达时刻和前车的到达时刻一致，即存在到达时刻为 D / speed_A。
• 后出发的快车没赶上先出发的慢车，即晚到的是后出发的慢车，这种情况其实和 speed_A >= speed_B 是一样的，即最后一辆车的到达时刻是 D / speed_B + 1。

那么我们是否需要真的去判断两辆车的速度大小关系，以及计算它们会否追及呢？答案是不需要。

可以看到，在只有两辆车的情况时，后车的到达时刻要么是 D / speed_B + 1，要么是 D / speed_A。在三个参数 D、speed_A、speed_B 已知的情况下，其到达时刻为上述两个算式中的较大值，即：

那么后车（两辆车中的最后一辆车）在路上的花费时间就是到达时刻 last_arrived 减去出发时刻 1，即：

多辆车的复杂情况

将两辆车的简单情况推广到多辆车的复杂情况。

已知第 i 辆车（索引从0开始）的速度为 speed_i，出发时间为 i 时。假设路上不存在任何其他车辆，单辆车的到达时刻为 D / speed_i + i。

由于所有车辆的出发时间和速度是独立的，不管怎么相遇、变速，最后一辆车到达终点的时间，实际上也取决于所有车中到达时刻最晚的那辆车。

假设所有车辆的速度依次储存在数组 speeds 中，那么最后一辆车的到达时刻应该为：

最后一辆车在路上的花费时间就是到达时刻 last_arrived 减去出发时刻 N-1，即：

这就规避了中间过程的复杂计算，而是通过数学逻辑推理，直接贪心地得到最后到达的车的花费时间。

浮点数输出的讨论

很显然，答案可能出现除不尽的小数，即需要输出浮点数。但本题并没有明确地告知需要保留几位小数，一般而言直接输出默认值即可。OJ系统的判题机，会自动计算输出答案和标准答案之间的误差，一般误差在 10^-4 内就算正确。

复杂度分析 设车辆数为 M（对应代码中读入的第一个数 N），起点到终点距离为 D。核心计算是对每辆车求 D / speed_i + i 并取最大值，Python 里是一次 max 生成式、C++ 里是一趟 for 循环，都只需遍历全部 M 辆车各一次，因此时间复杂度为 O(M)。空间上需要一个长度为 M 的 speeds 数组保存各车速度，空间复杂度为 O(M)。本题车辆数不超过 20、距离不超过 400，规模极小，任何写法都不会超时，这个解法的价值在于用一步取最大值绕开了逐一模拟追及过程的复杂讨论。

边界与注意事项

• 只有一辆车时公式同样成立：到达时刻为 D / speed，出发时刻为 0，花费时间就是 D / speed，无需特判。
• 答案可能除不尽，代码统一保留一位小数输出（Python 的 f"{ans:.1f}"、C++ 的 setprecision(1)）。
• 到达时刻与花费时间不要混淆：max 求出的是最后到达的时刻，还要减去最后一辆车的出发时刻（即车辆数减一）才是它在路上的时间，漏减这一步是最常见的错误。
• C++ 版把距离 D 声明为 double 读入，保证 D / speeds[i] 是浮点除法；若把 D 声明为 int，整数除法会直接算错。Python 的 / 本身就是浮点除法，没有这个问题。