题目链接

旺仔哥哥挤地铁

题目描述

这是一个函数实现题。你需要实现一个 countLongestSubwayTime 函数，计算旺仔哥哥从地铁 x 站到 y 站所花费的最长时间。

函数接受以下参数：

  • t: 一个整数数组，t[i] 表示地铁从第 i+1 站行驶到第 i+2 站的用时。
  • s: 一个整数数组，s[i] 表示地铁在第 i+1 站的停靠时间。
  • x, y: 两个正整数，表示起点和终点站的编号（1-indexed）。

最长时间的定义是：在始发站 x，地铁一到站就上车；在终点站 y，地铁即将发车时才下车。这意味着乘客完整地经历了从 x 站到 y 站（含两端）的所有停站时间，以及期间所有的行驶时间。

示例:

  • 输入: t=[150,180,170], s=[35,32,33,34], x=2, y=4
  • 你的函数应返回: 449
  • 说明:
    • 在第 2 站停靠 s[1]=32 秒。
    • 从第 2 站开到第 3 站用时 t[1]=180 秒。
    • 在第 3 站停靠 s[2]=33 秒。
    • 从第 3 站开到第 4 站用时 t[2]=170 秒。
    • 在第 4 站停靠 s[3]=34 秒。
    • 总时间 = 32 + 180 + 33 + 170 + 34 = 449。

解题思路

本题的核心在于精确地将问题描述中的时间累加过程转化为代码。我们需要将总时长分解为两部分：所有相关的行驶时间和所有相关的停靠时间。

  1. 索引转换: 题目给出的站台编号 x 和 y 是从 1 开始的 (1-indexed)，而 C++/Java/Python 中的数组索引是从 0 开始的 (0-indexed)。因此，在访问数组时需要进行转换：

    • 第 k 站的停靠时间对应数组 s 中的 s[k-1]。
    • 从第 k 站到第 k+1 站的行驶时间对应数组 t 中的 t[k-1]。

  2. 时间累加范围:

    • 停靠时间: 根据"最长时间"的定义，旺仔哥哥经历了从第 x 站到第 y 站（包含 x 和 y）的每一次停靠。所以，我们需要累加从 s[x-1] 到 s[y-1] 的所有停靠时间。
    • 行驶时间: 旺仔哥哥的旅程覆盖了从 x 站到 y 站之间的所有路段。即 x -> x+1, x+1 -> x+2, ..., y-1 -> y。对应的行驶时间是 t[x-1], t[x], ..., t[y-2]。

  3. 计算方法: 我们可以用一个循环来模拟这个过程，从而累加总时间。

    • 初始化一个 total_time 变量为 0。
    • 方法一 (分别累加):
      • 一个循环累加所有相关的停靠时间：for i from x to y, total_time += s[i-1]。
      • 另一个循环累加所有相关的行驶时间：for i from x to y-1, total_time += t[i-1]。
    • 方法二 (合并循环):
      • 我们可以设计一个更紧凑的循环，从 x 遍历到 y-1。在每次迭代 i 中，模拟从 i 站出发的完整过程：加上在 i 站的停靠时间 s[i-1]，再加上行驶到下一站 i+1 的时间 t[i-1]。
      • 循环结束后，总时间已经包含了 x 到 y-1 站的停靠时间和所有行驶时间。
      • 最后，只需额外加上在终点站 y 的停靠时间 s[y-1] 即可。

    两种方法都能得到正确结果，方法二在代码上更为简洁。

代码

注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算旺仔哥哥在地铁上的最长停留时间
     * @param t int整型vector 序列 t，表示地铁在相邻两站之间的用时
     * @param s int整型vector 序列 s，表示地铁在每一站的停靠时间
     * @param x int整型 旺仔哥哥想从第 x 站出发
     * @param y int整型 旺仔哥哥想坐到第 y 站
     * @return int整型
     */
    int countLongestSubwayTime(std::vector<int>& t, std::vector<int>& s, int x, int y) {
        // 假设 x < y
        long long total_time = 0;
        
        // 累加从 x 站到 y-1 站的停靠时间 和 x->y 的行驶时间
        for (int i = x; i < y; ++i) {
            // 停在第 i 站的时间 (s 的索引是 i-1)
            total_time += s[i - 1];
            // 从第 i 站开到 i+1 站的时间 (t 的索引是 i-1)
            total_time += t[i - 1];
        }
        
        // 最后加上在终点站 y 的停靠时间
        total_time += s[y - 1];
        
        return static_cast<int>(total_time);
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算旺仔哥哥在地铁上的最长停留时间
     * @param t int整型一维数组 序列 t，表示地铁在相邻两站之间的用时
     * @param s int整型一维数组 序列 s，表示地铁在每一站的停靠时间
     * @param x int整型 旺仔哥哥想从第 x 站出发
     * @param y int整型 旺仔哥哥想坐到第 y 站
     * @return int整型
     */
    public int countLongestSubwayTime(int[] t, int[] s, int x, int y) {
        // 假设 x < y
        long totalTime = 0;
        
        // 累加行驶时间和 x 到 y-1 站的停靠时间
        for (int i = x; i < y; i++) {
            // 停在第 i 站的时间 (s 的索引是 i-1)
            totalTime += s[i - 1];
            // 从第 i 站开到 i+1 站的时间 (t 的索引是 i-1)
            totalTime += t[i - 1];
        }
        
        // 加上终点站 y 的停靠时间
        totalTime += s[y - 1];
        
        return (int)totalTime;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算旺仔哥哥在地铁上的最长停留时间
# @param t int整型一维数组 序列  t，表示地铁在相邻两站之间的用时
# @param s int整型一维数组 序列 s，表示地铁在每一站的停靠时间
# @param x int整型 旺仔哥哥想从第 x 站出发
# @param y int整型 旺仔哥哥想坐到第 y 站
# @return int整型
#
class Solution:
    def countLongestSubwayTime(self, t: List[int], s: List[int], x: int, y: int) -> int:
        # 假设 x < y
        total_time = 0
        
        # 累加 x 到 y-1 站的停站时间，以及 x 到 y 站的行驶时间
        # 站号 i 对应 s 和 t 的索引是 i-1
        for i in range(x, y):
            total_time += s[i - 1] # 停在 i 站的时间
            total_time += t[i - 1] # 从 i 站开到 i+1 站的时间
            
        # 加上在终点 y 站的停站时间
        total_time += s[y - 1]
        
        return total_time

算法及复杂度

  • 算法: 线性扫描/模拟。
  • 时间复杂度: 。我们的循环从 x 运行到 y-1，迭代次数正比于乘坐的站数。在最坏情况下，x=1, y=N，复杂度为 ，其中 是总站数。
  • 空间复杂度: 。我们只使用了常数个额外变量（如 total_time 和循环变量 i）来计算结果。