题解：P1160 队列安排

yushyi · 2026-01-07 23:35:23 · 题解

思路

老师每次会添加一些同学在指定的位置，同时也会删除一些同学。也就是说我们需要使用一种增加或删除速度极快的数据结构来模拟出这个队列，那么这就是链表了，由于我们需要处理左右两边，所以我们使用的还需要是双向链表。然后就是模拟了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
int lt[N],nxt[N];// lt[i]: 元素i的前一个    nxt[i]: 元素i的下一个
bool vis[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,s = 1; // s是链表的头指针
    cin >> n;
    for(int i = 2;i <= n;i++){
        int k;
        bool p;
        cin >> k >> p;
        if(s == k && !p){
            // 放在当前头指针的左边，则将头指针更新为当前的学生
            s = i;
        }
        if(p){
            // 放右边
            if(nxt[k] != 0){
                lt[nxt[k]] = i;
            }
            nxt[i] = nxt[k];
            nxt[k] = i;
            lt[i] = k;
        } else{
            // 放左边
            if(lt[k] != 0){
                nxt[lt[k]] = i;
            }
            lt[i] = lt[k];
            lt[k] = i;
            nxt[i] = k;
        }
    }
    int m;
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        if(vis[x]){
            // x如果已经删除过了，则不重复删除x
            continue;
        }
        vis[x] = true;
        if(x == s){
            // 删除头指针，则更新头指针
            s = nxt[s];
        }
        if(lt[x] != 0){
            nxt[lt[x]] = nxt[x];
        }
        if(nxt[x] != 0){
            lt[nxt[x]] = lt[x];
        }
    }
    while(s != 0){
        // 遍历整个链表
        cout << s << " ";
        s = nxt[s];
    }
    return 0;
}