P4815 调度员的烦恼（基础）

解题思路

1. 理解车站结构。 车厢按 1、2、…、n 的顺序从 A 方向驶入，车站 C 可以临时停放任意多节车厢，但只能从一边进出，所以车站 C 就是一个栈：后进站的车厢在外面，必须先出来。这就像一列火车开进调度支线，车厢可以重新组合。
2. 目标顺序。 第二行给出期望从 B 方向驶出的顺序 target[1..n]。只要这个顺序能由"按 1..n 依次进站、随时可出站"的规则产生，就输出 YES。
3. 用栈模拟。 用数组模拟车站 C，top 表示当前停在 C 里的车厢数，nextCar 表示下一节还没进站的车厢编号。依次看每个目标车厢 need：只要栈顶不是 need，就让 nextCar 进站（压栈），nextCar 加一。
4. 判断失败。 如果 nextCar 已经超过 n，说明所有车厢都进站了，栈顶仍然不是 need，那就无法按这个顺序出站，输出 NO。
5. 成功出站。 当栈顶正好是 need 时，让它从 B 方向驶出（出栈），继续看下一个目标。全部目标都能满足，就输出 YES。

参考代码

// 调度员的烦恼：车厢按1到n依次从A方向进入车站C(栈)，用栈模拟判断能否按给定顺序从B方向驶出
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int target[1005];   // 期待从B方向驶出的车厢顺序
    for (int i = 1; i <= n; i++) cin >> target[i];
    int stack[1005];    // 模拟车站C的栈，可停放任意多节车厢
    int top = 0;        // 栈顶（当前停放在车站C中的车厢数）
    int nextCar = 1;    // 下一节还没进入车站C的车厢编号
    for (int i = 1; i <= n; i++) {
        int need = target[i];
        // 不断让下一节车厢进入车站C，直到最外面那节就是要驶出的车厢
        while (top == 0 || stack[top - 1] != need) {
            if (nextCar > n) {   // 全部车厢都已进站仍无法匹配
                cout << "NO" << endl;
                return 0;
            }
            stack[top++] = nextCar;
            nextCar++;
        }
        top--;   // 需要的那节车厢从栈顶驶向B方向
    }
    cout << "YES" << endl;
    return 0;
}

复杂度分析

每节车厢最多进站一次、出站一次，所以时间复杂度是 O(n)，n≤1000，非常快。空间上需要一个长度 n 的数组来存放 target 和模拟车站的栈，是 O(n)。即使 n 再大一些也完全没有压力。