题解 P1160 【队列安排】

· · 题解

嗯...终于找到一道链表模板题，顺便发波题解吧

蒟蒻一直都是用list的orzzzzz

首先，这道题我们看到是对一个数列进行频繁的插入和删除操作，这和链表正好是吻合的。

这里大佬们纷纷用的双向链表...于是想一想也写双向链表好了。

那么就说说其实现细节吧，因为我也纠结了很久。

由于个人喜好问题在下用的是结构体

struct node{
 int L, R;
}a[100003];

来作为链表节点的qwq

先看看删除：

我们把当前节点pos的左边节点a[pos].L的右边节点设置成a[pos.R]，也就是a[a[pos].L].R = a[pos].R，对右边节点也同样的处理，即a[a[pos].R].L = a[pos].L，这样在遍历这个链表的时候就可以跳过这个节点，最后再将该节点的左、右均设置成-1，就完成了删除操作。

inline void del(int x) {
    if(a[x].L == -1) return;
    a[a[x].L].R = a[x].R;
    a[a[x].R].L = a[x].L;
    a[x].L = -1;
    a[x].R = -1; 
}

再来看看如何插入节点。

将一个节点i插入pos的左边，

这样的四步之后就可以实现插入到左边的操作辣！

右边用相反的步骤完成即可。

完整的插入操作：

inline void addRight(int x, int pos) { //插入右边 
    a[x].L = pos;
    a[a[pos].R].L = x;
    a[x].R = a[pos].R;
    a[pos].R = x;
}
inline void addLeft(int x, int pos) { //插入左边
    a[x].R = pos;
    a[a[pos].L].R = x;
    a[x].L = a[pos].L;
    a[pos].L = x;
}

最后是遍历。一开始我开了个头指针，后来看了题解区的大佬，感觉好厉害w

由于我们的链表是从1开始的，我们不妨将节点0变为一切的开始，也就是将a[0].R=1,a[1].L=0这样的强行插入节点0

显然，在最后的时候i仍然是整个链表的第一个节点，这样还可以避免在插入时遇到链表开头的讨论。

所以遍历输出的代码就是：

inline void go() {
    int x = a[0].R;
    while(1) {
        cout<<x<<" ";
        if(a[x].R == -1) break;
        x = a[x].R;
    }
}

那么数组模拟双向链表就完成辣！

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    int L, R;
}a[100003];
int n, m;
inline void addRight(int x, int pos) { //插入右边 
    a[x].L = pos;
    a[a[pos].R].L = x;
    a[x].R = a[pos].R;
    a[pos].R = x;
}
inline void addLeft(int x, int pos) { //插入左边
    a[x].R = pos;
    a[a[pos].L].R = x;
    a[x].L = a[pos].L;
    a[pos].L = x;
}
inline void del(int x) {
    if(a[x].L == -1) return;
    a[a[x].L].R = a[x].R;
    a[a[x].R].L = a[x].L;
    a[x].L = -1;
    a[x].R = -1; 
}
inline void go() {
    int x = a[0].R;
    while(1) {
        cout<<x<<" ";
        if(a[x].R == -1) break;
        x = a[x].R;
    }
}
inline void init() {
    for(int i = 1; i <= n; ++i) a[i].L = a[i].R = -1;
    a[1].R = -1; a[1].L = 0; a[0].R = 1;
}
int main() {
    scanf("%d", &n);
    int cmd1, cmd2;
    init();
    for(int i = 2; i <= n; ++i) {
        scanf("%d %d", &cmd1, &cmd2);
        if(!cmd2) addLeft(i, cmd1);
        else addRight(i, cmd1);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d", &cmd1);
        del(cmd1);
    }
    go();
    return 0;
}