题目链接

火车站台

题目描述

在一条直线上有若干个城市，从左到右依次编号。存在 n 条火车路线，每条路线从城市 Y 出发，到达城市 X，其中 Y > X。火车会沿途停靠在 [X, Y-1] 区间内的所有城市。

我们需要找出所有城市中，停靠火车线路数最多的那个城市的停靠数是多少。

解题思路

1. 问题转化

这个问题可以被抽象为：给定 n 个左闭右开区间 [X_i, Y_i)，求数轴上哪个点被最多的区间所覆盖，并返回这个最大覆盖数。

2. 暴力解法 (及其问题)

一个直观的想法是创建一个数组 counts 来记录每个城市的停靠次数。数组的大小为最大城市编号。

对于每条路线 (X, Y)，我们遍历从 X 到 Y-1 的所有城市，并将它们在 counts 数组中对应的值加一。 最后，遍历 counts 数组找到最大值。

这种方法的时间复杂度为 ，其中 N 是路线数，M 是最大城市编号。在 N 和 M 都达到 的情况下，计算量过大，会导致超时。

3. 差分数组 (Difference Array) 优化

这是一个典型的“区间修改，单点查询”问题，可以使用差分数组来优化。

核心思想是，对一个区间 [L, R] 进行整体加一的操作，可以转化为在差分数组 diff 上进行两次单点修改：diff[L]++ 和 diff[R+1]--。

  • diff[L]++ 的意思是，从 L 点开始，其后的所有点（通过前缀和累加）的计数值都会增加 1。
  • diff[R+1]-- 的意思是，从 R+1 点开始，其后的所有点的计数值都会减少 1，从而抵消了 diff[L]++ 在 R+1 之后产生的影响，使得增加 1 的效果仅限于 [L, R] 区间。

对于本题的火车路线 (X, Y)，其停靠区间为 [X, Y-1]。因此，我们只需要执行 diff[X]++ 和 diff[Y]--。

4. 算法步骤

  1. 创建一个大小为 max_city_id + 2 的差分数组 diff，并初始化为 0。
  2. 遍历 n 条火车路线。对于每条路线 (X, Y)，执行 diff[X]++ 和 diff[Y]--。
  3. 处理完所有路线后，diff 数组记录了所有区间操作的净变化。
  4. 计算 diff 数组的前缀和。第 i 个城市 i 的最终停靠次数就是 diff 数组从 0 到 i 的累加和。
  5. 在计算前缀和的过程中，用一个变量 max_routes 实时记录遇到的最大值。
  6. 遍历结束后，max_routes 即为所求的答案。

这个算法将时间复杂度从 优化到了 。

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_CITY_ID = 100001;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> diff(MAX_CITY_ID + 2, 0);

    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        diff[x]++;
        diff[y]--;
    }

    int max_routes = 0;
    int current_routes = 0;
    for (int i = 1; i <= MAX_CITY_ID; ++i) {
        current_routes += diff[i];
        if (current_routes > max_routes) {
            max_routes = current_routes;
        }
    }

    cout << max_routes << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MAX_CITY_ID = 100001;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] diff = new int[MAX_CITY_ID + 2];

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            diff[x]++;
            diff[y]--;
        }

        int maxRoutes = 0;
        int currentRoutes = 0;
        for (int i = 1; i <= MAX_CITY_ID; i++) {
            currentRoutes += diff[i];
            if (currentRoutes > maxRoutes) {
                maxRoutes = currentRoutes;
            }
        }

        System.out.println(maxRoutes);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        
        MAX_CITY_ID = 100001
        diff = [0] * (MAX_CITY_ID + 2)
        
        for _ in range(n):
            x, y = map(int, sys.stdin.readline().split())
            diff[x] += 1
            diff[y] -= 1
            
        max_routes = 0
        current_routes = 0
        for i in range(1, MAX_CITY_ID + 1):
            current_routes += diff[i]
            if current_routes > max_routes:
                max_routes = current_routes
                
        print(max_routes)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：差分数组 (Difference Array)

  • 时间复杂度: ，其中 N 是火车路线的数量，M 是最大的城市编号。我们需要 的时间来处理所有路线并构建差分数组，然后需要 的时间来计算前缀和以找到最大值。

  • 空间复杂度: ，用于存储差分数组。