P4812 召见骑士（基础）

解题思路

1. 理解长廊规则。 5 位骑士的编号是 1、3、5、7、9，他们按编号从小到大的次序依次走进长廊。长廊只能从一边进出，所以它是一个栈：先进去的骑士在最里面，后进去的骑士在最外面。就像一摞盘子，最后放上去的盘子最先被拿走。
2. 要判断什么。 国王把想召见的骑士编号写在纸上，这个顺序就是骑士们"走出长廊"的顺序。我们要检查这个出栈顺序能不能由进栈顺序 1,3,5,7,9 实现。
3. 用栈模拟。 用一个数组当长廊，top 表示当前长廊里的骑士人数，idx 表示下一个还没进长廊的骑士在 order 中的位置。依次看召见序列里的每个编号 need：只要栈顶不是 need，就让下一个骑士进长廊；如果 5 位骑士全都进过长廊了，栈顶仍然不是 need，说明这个顺序根本做不到，输出 NO。
4. 找到就出栈。 当栈顶正好是 need 时，把他"召见"出来（top 减一），然后继续处理下一个要召见的编号。
5. 全部成功。 如果召见序列里的每一个编号都能这样匹配出来，就输出 YES。注意召见的可能只是部分骑士，所以不需要 5 位都出栈。

参考代码

// 召见骑士：骑士按1,3,5,7,9从小到大的次序依次进入长廊(栈)，用栈模拟判断国王的召见顺序是否合理
#include <iostream>
using namespace std;

int main() {
    int target[10];     // 国王写在纸上的召见顺序
    int cnt = 0;        // 召见序列中骑士的个数
    int num;
    while (cin >> num) {
        target[cnt++] = num;
    }
    int order[5] = {1, 3, 5, 7, 9};   // 骑士进入长廊的固定顺序
    int stack[10];        // 用数组模拟长廊（只能从一边进出，即栈）
    int top = 0;          // 当前长廊里的人数
    int idx = 0;          // 下一个还没进长廊的骑士在order中的下标
    for (int i = 0; i < cnt; i++) {
        int need = target[i];
        // 不断让后面的骑士进入长廊，直到长廊最里面那位就是要召见的骑士
        while (top == 0 || stack[top - 1] != need) {
            if (idx >= 5) {   // 所有骑士都进过长廊了仍找不到
                cout << "NO" << endl;
                return 0;
            }
            stack[top++] = order[idx++];
        }
        top--;   // 栈顶就是要召见的骑士，让他从长廊出来
    }
    cout << "YES" << endl;
    return 0;
}

复杂度分析

每个骑士最多进长廊一次、出长廊一次，所以整体是 O(n)，n 是召见序列里的骑士个数（最多 5 个）。无论怎么排序，模拟过程都很快。空间上只需要长度 10 左右的数组，几乎可以忽略。