PP4864 排队安排（基础）

解题思路

第一步，理解题意。 1 号同学先站好，2 到 N 号同学依次插到 k 号同学右边，队伍就排好了。然后老师又让 M 个同学离开队伍，如果某个同学已经不在队伍里，这条指令就忽略。最后从左到右输出剩下的同学编号。

第二步，选择数据结构。 既要插入又要删除，还要按顺序输出，用数组模拟双向链表最合适：pre[i] 记 i 左边是谁，nxt[i] 记 i 右边是谁，0 表示没有。再准备一个 del 数组记录谁已经被删掉。

第三步，模拟插入。 新同学 i 要插到 k 右边：先把 i 的左邻居设为 k、右邻居设为 k 原来的右边，然后把前后邻居的指针都指向 i。因为题目只让插右边，比"插左边"少了很多麻烦，队头不会变化。

第四步，模拟删除。 删除 x 时，如果 del[x] 已经是 1，直接忽略这条指令；否则标记 del[x]=1，然后"绕过" x：让 x 左边的同学的右边变成 x 原来的右边，让 x 右边的同学的左边变成 x 原来的左边。如果 x 是队头，还要把 head 移到 x 右边的人。

第五步，例子验证。 样例先排成 1 4 2 3，然后删除 3，剩下 1 4 2；再删 3 时发现已经删除就忽略，输出正是 1 4 2。

参考代码

// 排队安排：都插到右边，再按指令删除同学，输出剩下的队伍
#include <iostream>
using namespace std;

int pre[10005];  // pre[i] 表示 i 左边是谁
int nxt[10005];  // nxt[i] 表示 i 右边是谁
int del[10005];  // del[x]=1 表示 x 已被删除

int main() {
    int n, k, m, x;
    cin >> n;
    int head = 1;
    for (int i = 2; i <= n; ++i) {
        cin >> k;
        // 把 i 插到 k 的右边
        pre[i] = k;
        nxt[i] = nxt[k];
        if (nxt[k] != 0) pre[nxt[k]] = i;
        nxt[k] = i;
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x;
        if (del[x]) continue;  // 已被删除就忽略这条指令
        del[x] = 1;
        if (pre[x] == 0) {
            head = nxt[x];            // x 在队头，队头后移
            if (nxt[x] != 0) pre[nxt[x]] = 0;
        } else {
            nxt[pre[x]] = nxt[x];     // 绕过 x，把前后连起来
            if (nxt[x] != 0) pre[nxt[x]] = pre[x];
        }
    }
    for (int i = head; i != 0; i = nxt[i]) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

插入和删除每次只做常数次操作，遍历输出要 O(N)，所以总时间复杂度 O(N+M)，空间复杂度 O(N)。N 最大 10000，M 条删除指令也都瞬间完成。