这道题要求我们在保证火车不相撞的前提下，最小化所有火车的总晚点时间。我们可以通过动态规划结合贪心策略来解决这个问题，核心思路是对火车按时间排序后，分方向维护状态并转移。

问题分析

• 两个车站 A 和 B 之间只有一条轨道，火车从 A 到 B 或 B 到 A 耗时均为 T。
• 每趟火车必须在其预计时间 $t_i$ ​或之后出发，且不允许相向而行的火车同时在轨道上。
• 目标是最小化总晚点时间 $∑(a_i−t_i)$，其中$a_i$是实际出发时间。

解题思路

1. 排序与分组

将火车按预计出发时间 $t_i$升序排序（时间相同时不影响顺序），并将 A 出发的火车和 B 出发的火车分别存入数组 a 和 b。

2. 动态规划状态定义

我们定义：

• f[x][y][0]：处理完前 x 趟 A 出发的火车和前 y 趟 B 出发的火车后，最后一辆火车是 A→B 方向时的最小总晚点时间。
• f[x][y][1]：处理完前 x 趟 A 出发的火车和前 y 趟 B 出发的火车后，最后一辆火车是 B→A 方向时的最小总晚点时间。
• 辅助数组 F[x] 和 G[y]：分别记录仅处理前 x 趟 A 车或前 y 趟 B 车时的最小晚点时间，用于状态转移的快速更新。

3. 状态转移策略

我们按火车的预计时间从大到小处理（逆序处理），这样可以利用 “后续火车不影响当前火车的最早出发时间” 的性质，结合贪心策略推导状态转移：

• 处理 A 出发的火车： 假设当前处理第 x 趟 A 车（从后往前处理），需要考虑与之前 B 车的时间冲突。若前一辆是 B→A 方向的火车，则当前 A 车的最早出发时间至少为 “前一辆 B 车的到达时间（即前B车出发时间+T）”；若前一辆是 A→A 方向，则无冲突，最早出发时间为自身 $t_i$。
• 处理 B 出发的火车： 类似地，处理第 y 趟 B 车时，若前一辆是 A→B 方向的火车，则当前 B 车的最早出发时间至少为 “前一辆 A 车的到达时间（即前A车出发时间+T）”；若前一辆是 B→B 方向，则无冲突。

4. 核心算法步骤

1. 将 A、B 出发的火车分别排序，得到数组 a 和 b。
2. 生成逆序处理的优先级列表 P（按预计时间从大到小）。
3. 初始化动态规划数组 f、F、G，并逆序处理每趟火车，更新状态。
4. 最终答案为 f[0][0][0] 和 f[0][0][1] 的最小值。

代码详解

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int, int> pi;

const int inf = 1e18;
bool chmin(int &x, int y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, T;
    cin >> n >> T;
    vi a, b;
    rep(i, 0, n-1) { // 读取n趟火车
        char op;
        int t;
        cin >> op >> t;
        if (op == 'A') a.pb(t);
        else b.pb(t);
    }
    sort(a.begin(), a.end()); // A车按时间升序
    sort(b.begin(), b.end()); // B车按时间升序

    int p = a.size(), q = b.size();
    // 生成逆序处理的优先级列表P（按预计时间从大到小）
    vi P(n);
    iota(P.begin(), P.end(), 0);
    sort(P.begin(), P.end(), [&](int x, int y) {
        int valx = (x < p) ? a[x] : b[x - p];
        int valy = (y < p) ? a[y] : b[y - p];
        return valx > valy;
    });

    // f[x][y][0/1]：处理x趟A车、y趟B车后，最后方向为A→B/ B→A的最小晚点
    vector<vector<array<int, 2>>> f(p + 1, vector<array<int, 2>>(q + 1, {inf, inf}));
    vi F(p, inf), G(q, inf); // 辅助数组，记录仅处理A车或B车时的最小晚点
    f[p][q][0] = f[p][q][1] = 0; // 初始状态：无火车时晚点为0

    int x = p, y = q; // 当前剩余未处理的A车数量x，B车数量y
    for (int pos : P) {
        if (pos < p) { // 处理A车
            x--;
            int ct = a[x]; // 当前A车的预计时间
            int cost = 0, i = x + 1, j = y;
            F[x] = inf;

            // 模拟当前A车出发后，后续火车的时间冲突与晚点计算
            while (i < p || j < q) {
                int ci = i, cj = j;
                ct += T; // 假设当前A车按时出发，到达B的时间
                // 处理后续B车的晚点（若B车在ct前出发，会与当前A车相向碰撞）
                while (j < q && b[j] <= ct) {
                    cost += ct - b[j];
                    j++;
                }
                chmin(F[x], cost + f[i][j][1]); // 转移自最后方向为B→A的状态

                ct += T; // 假设当前A车晚点出发，到达B的时间（用于处理后续A车）
                // 处理后续A车的晚点（若A车在ct前出发，会与当前A车同向但需考虑时间）
                while (i < p && a[i] <= ct) {
                    cost += ct - a[i];
                    i++;
                }
                chmin(F[x], cost + f[i][j][0]); // 转移自最后方向为A→B的状态

                if (ci == i && cj == j) break; // 无新火车可处理，退出循环
            }

            // 更新f[x][y][0]（最后方向为A→B）
            int cf = F[x];
            rep(j, y, q) {
                chmin(f[x][j][0], f[x + 1][j][0]);
                chmin(f[x][j][0], cf);
                if (j < q) {
                    if (b[j] > a[x] + T) cf = inf;
                    else cf -= (a[x] + T) - b[j];
                }
            }

            // 更新f[x][y][1]（最后方向为B→A）
            per(j, q - 1, y) {
                chmin(f[x][j][1], f[x][j + 1][1]);
                G[j] += (b[j] + T) - a[x];
                chmin(f[x][j][1], G[j]);
            }
        } else { // 处理B车，逻辑与A车对称
            y--;
            int ct = b[y];
            int cost = 0, i = x, j = y + 1;
            G[y] = inf;

            while (i < p || j < q) {
                int ci = i, cj = j;
                ct += T;
                while (i < p && a[i] <= ct) {
                    cost += ct - a[i];
                    i++;
                }
                chmin(G[y], cost + f[i][j][0]);

                ct += T;
                while (j < q && b[j] <= ct) {
                    cost += ct - b[j];
                    j++;
                }
                chmin(G[y], cost + f[i][j][1]);

                if (ci == i && cj == j) break;
            }

            int cg = G[y];
            rep(i, x, p) {
                chmin(f[i][y][1], f[i][y + 1][1]);
                chmin(f[i][y][1], cg);
                if (i < p) {
                    if (a[i] > b[y] + T) cg = inf;
                    else cg -= (b[y] + T) - a[i];
                }
            }

            per(i, p - 1, x) {
                chmin(f[i][y][0], f[i + 1][y][0]);
                F[i] += (a[i] + T) - b[y];
                chmin(f[i][y][0], F[i]);
            }
        }
    }

    int ans = min(f[0][0][0], f[0][0][1]);
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：排序操作的时间复杂度为 $O(NlogN)$，动态规划状态转移的时间复杂度为$O(N^2)$（因为 p+q=N，且每个状态的转移操作是常数时间）。整体复杂度为 $O(N^2)$，可通过 N≤5000的数据范围。
• 空间复杂度：动态规划数组 f 的空间为 $O(p×q)$，辅助数组 F 和 G 的空间为 $O(p+q)$，整体为 $O(N^2)$，在题目限制下可接受。 该算法通过逆序处理和动态规划的结合，确保了在每一步都选择 “当前最优” 的晚点策略，最终得到全局最小的总晚点时间。