车厢调度(train)

题目描述

$n$ 节车厢按 $1,2,\dots,n$ 顺序从 A 驶入，经车站 C（栈）驶向 B。判断能否以给定顺序 $a_1,\dots,a_n$ 出站。 $n \le 1000$ 。

思路

车站 C 是栈。要让 $a_i$ 出站，所有编号 $\le a_i$ 且尚未出站的车厢必须先入栈。维护 cur（下一节未入栈车厢）和栈，对每个目标 $a_i$ ：若 $a_i \ge cur$ 则把 $cur..a_i$ 入栈；然后弹出栈顶，若栈顶不是 $a_i$ 则无解。全部成功输出 YES。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:30
# update_at: 2026-10-01 10:30

import sys


def solvable(a: list[int]) -> bool:
    """目标出站序列能否由 1..n 依次入站（车站 C 是栈）得到。"""
    stack: list[int] = []       # 车站 C：栈底是先入站的车厢
    cur = 1                     # 下一节还没进站的车厢编号
    for x in a:
        # 编号不超过 x 的车厢依次入栈；x < cur 时没有新车厢可入，cur 也不能回退
        if x >= cur:
            stack += range(cur, x + 1)
            cur = x + 1
        if not stack or stack.pop() != x:  # x 必须恰好是栈顶才能出站
            return False
    return True


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [next(data) for _ in range(n)]
    print("YES" if solvable(a) else "NO")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:52
 * update_at: 2026-10-05 11:52
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

int n;
int a[MAXN];
int stk[MAXN]; // 车站 C 模拟栈，stk[top] 为栈顶
int top;       // 栈顶指针，0 表示空栈

bool solvable() {
    int cur = 1; // 下一节还没进站的车厢编号
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        // 把 cur..x 依次入栈；x < cur 时无需入栈
        if (x >= cur) {
            for (int v = cur; v <= x; ++v) {
                stk[++top] = v;
            }
            cur = x + 1;
        }
        // 检查栈顶是否恰好为 x
        if (top == 0 || stk[top] != x) {
            return false;
        }
        --top; // 弹出 x
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    cout << (solvable() ? "YES" : "NO") << "\n";
    return 0;
}

目录

题目描述

思路

参考代码