本题练习地址：https://oj.algomooc.com/
一、题目描述与示例
题目描述
代码语言：javascript复制M (1 <= M <= 20)`辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为`N (1 <= N <= 400)
速度快的车追上前车后，只能以前车的速度继续行驶，求最后一车辆到达目的地花费的时间。
注:每辆车固定间隔1小时出发，比如第一辆车0时出发，第二辆车1时出发，依次类推
输入描述
第一行两个数字：M N分别代表车辆数和到终点的距离，以空格分隔。
接下来M行，每行1个数字 S，代表每辆车的速度。0 < S < 30
输出描述
输出:最后一辆车到达目的地花费的时间。
示例
输入
代码语言：javascript复制2 11
3
2
输出
代码语言：javascript复制5.5
说明
代码语言：javascript复制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
代码语言：javascript复制# 题目：【贪心】2023C-运输时间
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：贪心，脑筋急转弯
# 代码看不懂的地方，请直接在群上提问
# 输入车辆数目N，起点到终点的距离D
N, D = map(int, input().split())
# 构建speeds数组，speeds[i]表示第i时出发的车的速度
speeds = list()
for _ in range(N):
speeds.append(int(input()))
# 计算最后一辆车的到达时刻
last_arrived = max(D / speed i for i, speed in enumerate(speeds))
# 计算最后一辆车在路上行驶的花费时间输出
ans = last_arrived-(N-1)
print(ans)
Java
代码语言：javascript复制import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入车辆数目 N 和 起点到终点的距离 D
int N = scanner.nextInt();
int D = scanner.nextInt();
// 构建 speeds 数组，speeds[i] 表示第 i 时出发的车的速度
int[] speeds = new int[N];
for (int i = 0; i < N; i ) {
speeds[i] = scanner.nextInt();
}
// 计算最后一辆车的到达时刻
double lastArrived = Double.MIN_VALUE;
for (int i = 0; i < N; i ) {
double time = (double) D / speeds[i] i;
if (time > lastArrived) {
lastArrived = time;
}
}
// 计算最后一辆车在路上行驶的花费时间并输出
double ans = lastArrived - (N - 1);
System.out.println(ans);
}
}
C
代码语言：javascript复制#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, D;
cin >> N >> D;
// 构建 speeds 数组，speeds[i] 表示第 i 时出发的车的速度
vector<int> speeds(N);
for (int i = 0; i < N; i ) {
cin >> speeds[i];
}
// 计算最后一辆车的到达时刻
double lastArrived = -1;
for (int i = 0; i < N; i ) {
double time = static_cast<double>(D) / speeds[i] i;
lastArrived = max(lastArrived, time);
}
// 计算最后一辆车在路上行驶的花费时间并输出
double ans = lastArrived - (N - 1);
cout << ans << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。单次循环所花费的时间
空间复杂度：O(1)。仅需若干常数变量
