华为机试题-单车道汽车通行时间-Java

代码在最后面

1 题目描述

M（1 ≤ M ≤ 20）辆车需要在一条不能超车的单行道到达终点，起点到终点的距离为 N（1 ≤ N ≤ 400）。

速度快的车追上前车后，只能以前车的速度继续行驶，求最后一辆车到达目的地花费的时间。

注：每辆车固定间隔 1 小时出发，比如第一辆车 0 时出发，第二辆车 1 时出发，依次类推

2 输入描述

第一行两个数字：M N，分别代表车辆数和到终点的距离，以空格分隔。
接下来 M 行，每行一个数字 S，代表每辆车的速度。
0 < S < 30

3 输出描述

最后一辆车到达目的地花费的时间

4 示例

4.1 示例1

输入	
2 10
4
2
输出	
5

解释：
第一行，表示2辆车，起点到终点的距离为10个单位。
第一辆车的速度为4，则第一辆车到终点的时间 2.5 = 10 / 4
第二辆车的速度为2，则第二辆车到终点的时间 5 = 10 / 2
由于第一辆车比第二辆车快，所以不存在阻塞问题，即最终答案为 5

4.1 示例2

输入	
2 10
2
4
输出	
4

解释：
第一行，表示2辆车，起点到终点的距离为10个单位。
第一辆车的速度为2，则第一辆车到终点的时间 5 = 10 / 2
第二辆车的速度为4，则第二辆车到终点的时间 2.5 = 10 / 4
由于第一辆车比第二辆车慢，所以存在阻塞问题，第二辆车并不能用2.5个时间单位到达目的地。但由于车辆是每隔1个时间单位出发, 1 + 2.5 = 3.5 < 5，所以第二辆车的到车时间是 5，但发车时间为 1，即第二辆车用时 4 = 5 -1 个时间单位。

5 代码解题

第二个示例是我写的，其实根据第二个示例就能看出来，这个题怎么解了。
假设没有阻塞问题，即后一辆车不会被前一辆车阻塞，只考虑发车时间和车速。
记当前发车为第 i 辆车，发车时间则为 start = i - 1，记车速为 v，记总路程为 S（也就是N），那么可以计算出每辆车到达终点的最终时间点为 h = start + S / v = i - 1 + S / v。【最终时间不是车辆通过路段的用时，而是一个时间点】
然后代入阻塞问题中，已知后一辆车会被前一辆车阻塞，记MaxH为所有车到达终点的时间最大值，记第X辆车到终点的时间为 MaxH。那么可以得出结论，1..X辆车必定在MaxH之前到达，不考虑， X..M辆车必定不能在MaxH之前到达终点。由此可以计算出，最后一辆车的用时为 T = MaxH -start = MaxH - (i - 1)
代入示例二，进行思路验证：

2 10 // 两辆车，路程10个单位
2 // 第一辆车，0点发车，车速单位为2，最终到达终点时间点 5 = 0 + 10 / 2
4 // 第一辆车，1点发车，车速单位为4，最终到达终点时间点 3.5 = 1 + 10 / 4
--- 代入上述公式
所有车到达终点的时间最大值 MaxH = 5
最后一辆车用时 T = MaxH - (i - 1) = 5 - (2 - 1) = 4
符合预期，完美

解题代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String line = scanner.nextLine();String[] split = line.split(" ");final int M = Integer.parseInt(split[0]);final int N = Integer.parseInt(split[1]);double maxH = 0;// i 表示发车时间，i + 1 表示发车序号，i = 0 < M 循环也是 M 次，所以省略车序号计算for (int i = 0; i < M; i++) {// 车速度int v = scanner.nextInt();maxH = Math.max(maxH, (double) N / v + i);}// M - 1 表示最后一辆车发车时间点double time = maxH - (M - 1);scanner.close();System.out.println(time);}
}