luogu-P1160 队列安排

GESP C++ 五级练习题，链表数据结构考点应用，五级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1160 队列安排

题目要求

题目描述

一个学校里老师要将班上 $N$ 个同学排成一列，同学被编号为 $1\sim N$ ，他采取如下的方法：
先将 $1$ 号同学安排进队列，这时队列中只有他一个人；
$2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；
从队列中去掉 $M$ 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 $N$ ，表示了有 $N$ 个同学。
第 $2\sim N$ 行，第 $i$ 行包含两个整数 $k,p$ ，其中 $k$ 为小于 $i$ 的正整数， $p$ 为 $0$ 或者 $1$ 。若 $p$ 为 $0$ ，则表示将 $i$ 号同学插入到 $k$ 号同学的左边， $p$ 为 $1$ 则表示插入到右边。
第 $N+1$ 行为一个整数 $M$ ，表示去掉的同学数目。
接下来 $M$ 行，每行一个正整数 $x$ ，表示将 $x$ 号同学从队列中移去，如果 $x$ 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

输入输出样例 #1

输入 #1

输出 #1

2 4 1

说明/提示

【样例解释】

将同学 $2$ 插入至同学 $1$ 左边，此时队列为：

2 1

将同学 $3$ 插入至同学 $2$ 右边，此时队列为：

2 3 1

将同学 $4$ 插入至同学 $1$ 左边，此时队列为：

2 3 4 1

将同学 $3$ 从队列中移出，此时队列为：

2 4 1

同学 $3$ 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 $20\%$ 的数据， $1\leq N\leq 10$ 。

对于 $40\%$ 的数据， $1\leq N\leq 1000$ 。

对于 $100\%$ 的数据， $1<M\leq N\leq 10^5$ 。

题目分析

本题主要考察链表的操作。

由于题目中涉及到频繁的插入和删除操作：

插入：需要将一个同学插入到另一个同学的左边或右边。
删除：需要将一个同学从队列中移出。

如果使用数组（Array）或 std::vector 进行模拟，每次在数组中间插入或删除元素都需要搬移后续所有元素，时间复杂度为 $O(N)$ 。在 $N=10^5$ 的情况下，总的时间复杂度可能达到 $O(N^2)$ ，这会导致超时。

因此，最合适的数据结构是 双向链表。链表可以在 $O(1)$ 的时间内完成节点的插入和删除。

每个节点记录其左边节点（l）和右边节点（r）的编号。
插入时，只需要修改相关节点的指针（l 和 r 数组的值）。
删除时，只需将其左邻居指向其右邻居，其右邻居指向其左邻居即可。

具体实现细节：

使用数组模拟链表：利用 l[i] 和 r[i] 两个数组分别存储同学 $i$ 左边和右边的同学编号。这种静态链表的方式编写简单，效率高。
边界处理：使用 0 表示没有邻居（即队头或队尾）。
重复删除处理：题目可能会要求删除已经不在队列中的同学，代码中使用 deleted 数组记录状态，避免重复操作。
队头维护：由于队头前面的元素可能会被插入新元素（变成新队头），或者队头元素被删除，因此需要维护一个 head 变量指向当前的队头，以便最后遍历输出。

结构体实现方案

除了使用独立的数组 l 和 r，还可以使用结构体 struct 来封装每个节点的属性（左指针、右指针、删除标记）。这种方式代码逻辑封装性更好，更符合面向对象的思维，但在本题这种简单的链表操作中，效率和数组模拟基本一致。

示例代码

数组实现方案

#include <iostream>

int l[100005];
int r[100005];
bool deleted[100005];
int main() {
    int N;
    std::cin >> N;
    l[1] = 0;
    r[1] = 0;
    int head = 1;
    for (int i = 2; i <= N; i++) {
        int k, p;
        std::cin >> k >> p;

        if (p == 0) {
            // 将 i 插入到 k 的左边
            if (l[k] == 0) {
                head = i;  // 如果 k 原来是头，即 l[k] == 0，既然 i 到了 k
                           // 左边，i 变成新头
            }
            // 链接 i 和 k 的左邻居（如果存在）
            if (l[k] != 0) {
                r[l[k]] = i;  // k 的左邻居的右边现在是 i
            }
            l[i] = l[k];  // i 的左边是 k 原来的左边

            // 链接 i 和 k
            l[k] = i;  // k 的左边现在是 i
            r[i] = k;  // i 的右边现在是 k

        } else {
            // 将 i 插入到 k 的右边
            if (r[k] != 0) {
                l[r[k]] = i;  // k 的右邻居的左边现在是 i
            }
            r[i] = r[k];  // i 的右边是 k 原来的右边

            // 链接 k 和 i
            l[i] = k;  // i 的左边是 k
            r[k] = i;  // k 的右边是 i
        }
    }

    int M;
    std::cin >> M;
    // 使用 deleted 数组标记是否已删除，避免重复处理

    while (M--) {
        int x;
        std::cin >> x;
        if (deleted[x]) {
            continue;  // 如果 x 已经不在队列中，忽略
        }
        deleted[x] = true;

        // 处理头节点情况
        if (head == x) {
            head = r[x];  // 头节点后移
        }

        // 1. 如果 x 有左邻居，让左邻居的右指针指向 x 的右邻居
        if (l[x] != 0) {
            r[l[x]] = r[x];
        }
        // 2. 如果 x 有右邻居，让右邻居的左指针指向 x 的左邻居
        if (r[x] != 0) {
            l[r[x]] = l[x];
        }

        // 清空 x 的指针（可选，但为了调试清晰保留）
        l[x] = 0;
        r[x] = 0;
    }

    // 输出队列
    int curr = head;
    while (curr != 0) {
        std::cout << curr << ' ';
        curr = r[curr];
    }

    return 0;
}

结构体实现代码

#include <iostream>

// 使用结构体定义节点
struct Node {
    int l, r;      // 左、右邻居的编号
    bool deleted;  // 删除标记
} nodes[100005];

int main() {
    int N;
    std::cin >> N;

    // 初始化 1 号节点
    nodes[1].l = 0;
    nodes[1].r = 0;
    nodes[1].deleted = false;
    
    int head = 1; // 维护队头

    for (int i = 2; i <= N; i++) {
        int k, p;
        std::cin >> k >> p;
        nodes[i].deleted = false;

        if (p == 0) {
            // 将 i 插入到 k 的左边
            // 1. 设置 i 的左右指针
            nodes[i].l = nodes[k].l;
            nodes[i].r = k;
            
            // 2. 更新 k 左邻居的右指针 (如果存在)
            if (nodes[k].l != 0) {
                nodes[nodes[k].l].r = i;
            } else {
                // k 原本是队头，现在 i 插在 k 左边，i 变成新队头
                head = i;
            }
            
            // 3. 更新 k 的左指针
            nodes[k].l = i;

        } else {
            // 将 i 插入到 k 的右边
            // 1. 设置 i 的左右指针
            nodes[i].l = k;
            nodes[i].r = nodes[k].r;
            
            // 2. 更新 k 右邻居的左指针 (如果存在)
            if (nodes[k].r != 0) {
                nodes[nodes[k].r].l = i;
            }
            
            // 3. 更新 k 的右指针
            nodes[k].r = i;
        }
    }

    int M;
    std::cin >> M;
    while (M--) {
        int x;
        std::cin >> x;
        if (nodes[x].deleted) {
            continue;
        }
        nodes[x].deleted = true;

        // 如果删除的是头节点，更新头节点
        if (head == x) {
            head = nodes[x].r;
        }

        // 链接 x 的左邻居和右邻居
        if (nodes[x].l != 0) {
            nodes[nodes[x].l].r = nodes[x].r;
        }
        if (nodes[x].r != 0) {
            nodes[nodes[x].r].l = nodes[x].l;
        }
    }

    // 从头遍历输出
    int curr = head;
    while (curr != 0) {
        std::cout << curr << " ";
        curr = nodes[curr].r;
    }

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年1月5日

luogu-P1865 A % B Problem