PP4863 指定队列（基础）

解题思路

第一步，理解题意。 1 号同学先站在队伍里。接着 2 到 N 号同学依次来排队，每人给出 (k, p)：p=0 表示站到 k 号同学的左边，p=1 表示站到右边。所有人都站好后，从左到右输出所有同学的编号。

第二步，想到双向链表。 同学只会站到某个人左边或右边，这是典型的链表插入。我们用 pre 和 nxt 两个数组模拟双向链表：pre[i] 记 i 左边是谁，nxt[i] 记 i 右边是谁，用 0 表示"没有"，再用 head 记住最左边是谁。

第三步，分两种情况插入。 插到 k 右边时，先让 i 的左边指向 k、右边指向 k 原来的右边，再把前后两个邻居接上 i。插到 k 左边时类似，但要注意：如果 k 本来就在队头，head 要换成 i，否则 head 指向的就不是最左边的人了。

第四步，例子验证。 样例 N=6：2 站 1 左边，3 站 1 右边，4 站 2 左边，5 站 3 右边，6 站 2 右边，最后队伍是 4 2 6 1 3 5，和输出完全一致。

第五步，边界情况。 k 一定是比 i 小的编号，所以插入时 k 一定已经在队伍里，不会出现"找不到人"的情况；N 最大 10000，数组开 10005 足够。

参考代码

// 指定队列：每个同学插到指定同学的左边或右边，数组模拟双向链表
#include <iostream>
using namespace std;

int pre[10005];  // pre[i] 表示 i 左边是谁，0 表示没有
int nxt[10005];  // nxt[i] 表示 i 右边是谁，0 表示没有

int main() {
    int n, k, p;
    cin >> n;
    int head = 1;  // 一开始队头是 1 号
    for (int i = 2; i <= n; ++i) {
        cin >> k >> p;
        if (p == 0) {
            // 插到 k 的左边
            nxt[i] = k;
            pre[i] = pre[k];
            if (pre[k] == 0) head = i;  // k 原来在队头，队头换成 i
            else nxt[pre[k]] = i;
            pre[k] = i;
        } else {
            // 插到 k 的右边
            pre[i] = k;
            nxt[i] = nxt[k];
            if (nxt[k] != 0) pre[nxt[k]] = i;
            nxt[k] = i;
        }
    }
    for (int i = head; i != 0; i = nxt[i]) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

每个同学只做几次赋值就能完成插入，遍历输出也只要 O(N) 次，所以总时间复杂度 O(N)，空间复杂度 O(N)。N 最大 10000，轻松通过。