题解 P3406 【海底高铁】

· · 题解

对于其中一小段，我们要么全部买纸票，要么全部刷卡。

所以我们只需要统计每一小段经过的总次数。

如果你暴力模拟统计的话，估计会tle。

怎么快速知道每一段次数呢？

我们回忆一下“借教室”这道题。

如果你高兴的话，可以上线段树或者树装数组——但是没必要。

假设有5段，我们把1到3加上1，可以像图2一样，开头+1，结尾-1。然后2到4加1，如图3.

                  +1      -1          +1 +1   -1 -1
 - - - - -        --  - - -- -        -- -- - -- --
 1 2 3 4 5        1   2 3 4  5        1  2  3 4  5
 图1              图2                 图3

然后呢，我们求出每一项前缀和（就是从前往后加）：

1 2 2 1 0
- - - - -
1 2 3 4 5
图4

然后每一段直接贪心比较，然后就没有然后了。