B4343 [语言月赛 202506] 地铁跑酷 题解

· · 题解

Source & Knowledge

2025 年 6 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定 n 个车站和它们之间的行车时间。一些车站会短暂停留，停靠时间和停靠车站已知。你需要计算从第 s 站上车到第 t 站下车，你一共在车上花费了多少时间。需要注意的是，上下车站点的停靠时间不计入总时间，只有中间经过的停靠站才计算停靠时间。

题目分析

首先，我们来拆解总时间：总时间 = 行车时间 + 停靠时间。

1. 计算行车时间

从第 s 站上车，到第 t 站下车，列车会经过 s 到 s+1, s+1 到 s+2, \dots, t-1 到 t 这一系列的路段。因此，行车时间就是这些路段的时间总和。我们可以通过一个循环，从 i=s 到 t-1 遍历，累加 a_i 即可。

long long total_travel_time = 0;
for (int i = s; i < t; ++i) {
   total_travel_time += a[i];
}

2. 计算停靠时间

题目中明确指出，只有中间经过的车站才计算停靠时间，即第 s 站和第 t 站的停靠时间不计入总时间。这意味着，对于每一个已知的停靠车站 b_j，我们都需要检查它是否在 s \sim t 内。如果 b_j > s 且 b_j < t，那么它就是一个中间经过的停靠站，其对应的停靠时间 c_j 应该被加到总时间中。

long long total_stop_time = 0;
for (int i = 1; i <= k; ++i) {
   if (b[i] > s && b[i] < t) {
      total_stop_time += c[i];
   }
}

将这两部分时间相加，即为最终的答案。

最后，n, k 的最大值为 10^5。任何一个总时间都可能达到近似 \approx 10^{10}，因此需要注意使用 long long 类型来存储，以防止溢出。