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

Source & Knowledge

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

给定

n

个车站和它们之间的行车时间。一些车站会短暂停留，停靠时间和停靠车站已知。你需要计算从第

s

站上车到第

t

站下车，你一共在车上花费了多少时间。需要注意的是，上下车站点的停靠时间不计入总时间，只有中间经过的停靠站才计算停靠时间。

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

从第

s

站上车，到第

t

站下车，列车会经过

s

到

s+1

s+1

到

s+2, \dots, t-1

到

t

这一系列的路段。因此，行车时间就是这些路段的时间总和。我们可以通过一个循环，从

i=s

到

t-1

遍历，累加

a_i

即可。

CPP

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

题目中明确指出，只有中间经过的车站才计算停靠时间，即第

s

站和第

t

站的停靠时间不计入总时间。这意味着，对于每一个已知的停靠车站

b_j

，我们都需要检查它是否在

s \sim t

内。如果

b_j > s

且

b_j < t

，那么它就是一个中间经过的停靠站，其对应的停靠时间

c_j

应该被加到总时间中。

CPP

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 类型来存储，以防止溢出。