洛谷-P1160 队列安排 题解

题目分析

这是一个关于队列构建和修改的问题。老师需要按照特定规则将N个同学排成一列，然后移除指定的M个同学，最后输出队列中剩余同学的编号。

解题思路

核心算法

使用单向链表来维护队列结构，通过维护一个指针数组来快速定位每个同学在链表中的前驱节点。

关键点

1. 链表构建：每个新同学插入到已有同学的左边或右边
2. 快速定位：使用数组arr记录每个编号对应的节点指针，实现O(1)时间复杂度的节点访问
3. 删除操作：通过前驱节点直接修改指针关系，实现O(1)时间复杂度的删除

核心思想

链表 + 前驱指针数组的复合数据结构

关键思路分析

1. 数据结构选择

• 使用单向链表：便于动态插入和删除操作
• 维护前驱指针数组：arr[i]记录编号i的同学在链表中的前驱节点指针
• 头节点技巧：使用哑节点简化边界条件处理

2. 删除操作优化

• 通过前驱数组直接定位要删除节点的前驱
• 修改指针关系实现O(1)删除
• 标记已删除节点（设为nullptr）避免重复删除

3. 算法流程

1. 初始化：建立头节点和1号同学
2. 构建队列：依次插入2~N号同学
3. 删除处理：移除指定同学，更新指针关系
4. 结果输出：遍历链表输出剩余同学

算法复杂度分析

• 时间复杂度：O(N + M)

构建队列：每个同学插入操作O(1)，共O(N)

删除同学：每个删除操作O(1)，共O(M)

输出结果：O(N)

• 空间复杂度：O(N)链表节点存储：O(N)指针数组：O(N)

代码实现详解

#include<iostream>
#include<vector>using namespace std;
struct Node 
{
int val;        // 存储同学编号
Node* next;     // 指向下一个节点
Node(int v) : val(v), next(nullptr) {}Node() : val(0), next(nullptr) {}
};

vector<Node*> arr(100001, nullptr);  // 指针数组，记录每个编号对应的节点前驱

int main() 
{
// 初始化链表，创建头节点和1号同学
Node* head = new Node(0);
head->next = new Node(1);arr[1] = head;  // 1号同学的前驱是头节点
int n, m;
cin >> n;
int index, flag;
Node* tmp;

// 构建队列：2~n号同学依次插入
for (int i = 2; i <= n; i++) {
    Node* cur = new Node(i);  // 创建新同学节点
    cin >> index >> flag;     // 读取插入位置和方向
    
    tmp = arr[index];  // 找到目标同学的前驱
    
    if (flag) {  // 插入到右边
        tmp = tmp->next;  // 移动到目标同学本身
    }
    // 此时tmp指向新同学应该插入位置的前一个节点
    
    arr[i] = tmp;  // 记录新同学的前驱
    
    if (tmp->next)  // 如果tmp后面有同学，更新其后继的前驱指针
        arr[tmp->next->val] = cur;
        
    // 执行插入操作
    cur->next = tmp->next;
    tmp->next = cur;
}

// 删除操作
cin >> m;
for (int i = 0; i < m; i++) {
    cin >> index;
    tmp = arr[index];  // 找到要删除同学的前驱
    
    if (tmp && tmp->next) {  // 如果同学存在且未被删除
        arr[tmp->next->val] = nullptr;  // 标记为已删除
        
        if (tmp->next->next)  // 更新后继同学的前驱指针
            arr[tmp->next->next->val] = tmp;
            
        tmp->next = tmp->next->next;  // 从链表中移除
    }
}

// 输出结果
tmp = head->next;
while (tmp) {
    cout << tmp->val << ' ';
    tmp = tmp->next;
}

return 0;
}