本题练习地址：https://oj.algomooc.com/
一、题目描述与示例
题目描述
M (1 <= M <= 20)`辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为`N (1 <= N <= 400)
速度快的车追上前车后，只能以前车的速度继续行驶，求最后一车辆到达目的地花费的时间。
注:每辆车固定间隔
1
小时出发，比如第一辆车
0
时出发，第二辆车
1
时出发，依次类推
输入描述
第一行两个数字：
M N
分别代表车辆数和到终点的距离，以空格分隔。
接下来
M
行，每行
1
个数字
S
，代表每辆车的速度。
0 < S < 30
输出描述
输出:最后一辆车到达目的地花费的时间。
示例
输入
2 11
3
2
输出
5.5
说明
2`辆车，距离`11`，`0`时出发的车速度快，`1`时出发的车慢，达到目的地花费`5.5
二、解题思路
本题题意虽然容易理解，但是乍一看相当复杂，像小学奥数会学习的那种追及问题。
如果真的去计算车辆之间相遇的时间和位置，那会算得非常痛苦。
概念辨析
需要注意本题存在两个概念需要进行辨析，
到达时刻
和
花费时间
。
到达时刻
指的是以某辆车以第
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 = max(D/speed_A, D/speed_B+1)
那么后车（两辆车中的最后一辆车）在路上的
花费时间
就是
到达时刻
last_arrived
减去
出发时刻
1
，即
ans = last_arrived - 1
多辆车的复杂情况
将两辆车的简单情况推广到多辆车的复杂情况。
已知第
i
辆车（索引从
0
开始）的速度为
speed_i
，出发时间为
i
时。
假设路上不存在任何其他车辆，单辆车的
到达时刻
为
D / speed_i + i
。
由于所有车辆的出发时间和速度是独立的，
不管怎么相遇、变速，最后一辆车到达终点的时间，实际上也取决于所有车中到达时刻最晚的那辆车
。
假设所有车辆的速度依次储存在数组
speeds
中，那么最后一辆车的
到达时刻
应该为
last_arrived = max(D / speed + i for speed in speeds)
最后一辆车在在路上的
花费时间
就是
到达时刻
last_arrived
减去
出发时刻
N-1
，即
ans = last_arrived - (N-1)
这就规避了中间过程的复杂计算，而是通过数学逻辑推理，直接
贪心地
得到最后到达的车的时间。
浮点数输出的讨论
很显然，答案可能出现除不尽的小数，即需要输出浮点数。
但本题并没有明确地告知需要保留几位小数，一般而言直接输出默认值即可。
OJ系统的判题机，会自
动计算输出答案和标准答案之间的误差
，一般误差在
10^-4
内就算正确。
三、代码
Python
# 题目：【贪心】2023C-运输时间
# 分值：200
