返回目录

题目描述

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

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

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

输入描述

第一行两个数字：M N，分别代表车辆数和到终点的距离，以空格分隔

接下来 M 行，每行一个数字 S，代表每辆车的速度。0 < S < 30

输出描述

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

示例：

题目解析

本题需要注意的是：速度快的车追上前车后，是可以和前车并行的。即本题的：

一条不能超车的单行道

指的应该是"单向"车道，即可能有多条单向车道，支持多辆车并行。

因此本题的解题就很简单了，由于后车不能超过前车，因此：

• 如果后车正常行驶情况下，比前车更早到达，则会被前车阻碍，此时后车到达终点时刻，和前车一致
• 如果后车正常行驶情况下，比前车更晚到达，则不会被前车阻碍，此时后车到达终点时刻，就是自己正常行驶到达终点的时刻

本题要求输出的是：到达目的地花费的时间 = 到达时刻 - 出发时刻

另外，需要注意，本题输出可能是小数，但是本题并没有说保留几位有效小数，我这边默认保留3位有效小数，四舍五入，实际考试时视情况改动。

Python算法源码

import math

# 输入m和n
m, n = map(int, input().split())

# 初始化到达终点的最晚时刻
arrived = 0

# 遍历每辆车
for i in range(m):
    # 输入当前车的速度
    speed = float(input())
    # 更新到达终点的最晚时刻
    # n/speed是行驶花费的时间，i是第i辆车的出发时间
    # 当前车如果比前车更早到达，则被前车阻碍，按前车到达时间算
    # 当前车如果比前车更晚到达，则不被前车阻碍，按后车到达时间算
    arrived = max(arrived, n / speed + i)

# 计算路上花费的时间
cost = arrived - (m - 1)

# 输出结果
print(cost)

C算法源码

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    // 记录前车到达终点的时刻，本题后车不可能比前车更早到达，因此如果后车到达时刻 < 前车到达时刻arrived，则后车也是按照前车arrived时刻达到
    double arrived = 0;

    for (int i = 0; i < m; i++) {
        // 当前车的速度
        int speed;
        scanf("%d", &speed);
        // 当前车到达终点的时刻
        // * 当前车如果比前车更早到达，则被前车阻碍，按前车到达时间算
        // * 当前车如果比前车更晚到达，则不被前车阻碍，按后车到达时间算
        arrived = arrived > (n / (double)speed + i) ? arrived : (n / (double)speed + i); // n*1.0/speed是行驶花费时间； i是第i辆车的出发时间
    }

    // 到达时刻 - 出发时刻 = 路上花费的时间
    double cost = arrived - (m - 1);

    printf("%.10lf\n", cost); // 实际考试没有精度问题，可以直接输出cost，可以满分
    // printf("%.3lf\n", cost); // 我这边OJ用例设计时有小数位则至多保留3位

    return 0;
}

Java算法源码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        // 记录前车到达终点的时刻，本题后车不可能比前车更早到达，因此如果后车到达时刻 < 前车到达时刻arrived，则后车也是按照前车arrived时刻达到
        double arrived = 0;

        for (int i = 0; i < m; i++) {
            // 当前车的速度
            int speed = Integer.parseInt(br.readLine());
            // 当前车到达终点的时刻
            // * 当前车如果比前车更早到达，则被前车阻碍，按前车到达时间算
            // * 当前车如果比前车更晚到达，则不被前车阻碍，按后车到达时间算
            arrived = Math.max(arrived, n / (double)speed + i); // n*1.0/speed是行驶花费时间； i是第i辆车的出发时间
        }

        // 到达时刻 - 出发时刻 = 路上花费的时间
        double cost = arrived - (m - 1);

        System.out.println(cost); // 实际考试没有精度问题，可以直接输出cost，可以满分
        // System.out.printf("%.3f%n", cost); // 我这边OJ用例设计时有小数位则至多保留3位
    }
}