华为OD 机试 - 运输时间（Java & Python & C++）

五分钟学算法

发布于 2024-04-14 09:01:40

2490

发布于 2024-04-14 09:01:40

文章被收录于专栏：五分钟学算法

本题练习地址：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
# 作者：闭着眼睛学数理化
# 算法：贪心，脑筋急转弯
# 代码看不懂的地方，请直接在群上提问


# 输入车辆数目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

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++

#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;
}