题解 P1160 【队列安排】

· · 题解

看了一下题解区似乎没有用STL的，那我就发个STL的解法好了(〃'▽'〃)

C++标准库自带了std::list这个双向链表的模板类，使用时需要包含头文件：#include <list>。

list<int> myList;

这句代码声明了一个list<int>类型的变量，也就是一个包含int类型元素的双向链表。尖括号里边的部分称为模板参数，对于list而言，它表示链表里的元素是什么类型。

myList.push_front(1);
myList.push_back(2);

顾名思义，这两个成员函数分别用于在链表的头部和尾部插入元素。对应地，pop_front()用于移除头部的元素，pop_back()用于移除尾部的元素。

typedef list<int>::iterator Iter;
Iter itBegin = myList.begin();
Iter itEnd = myList.end();
for (; itBegin != itEnd; ++itBegin)
    printf(" %d", *itBegin);

这段代码演示的是list提供的，用于访问内部元素的迭代器。迭代器的类型是list<Tp>::iterator（这里模板参数Tp需要与你操作的链表一致）。

迭代器的用法和指针有些像，可以用*运算符访问内部的元素，++和--运算符可以将它后移或前移一位（建议写成前置形式），用==和!=运算符进判断两个迭代器所指的位置是否一致。但要注意：list的迭代器不支持it += x或it1 - it2这样的运算，也不支持<，<=等运算符。

begin()成员函数返回指向头部元素的迭代器。

end()成员函数返回指向末尾位置的迭代器。这个“末尾位置”指的是最后一个元素再往后一位，也就是说end()所指的位置不包含有效元素，它相当于一个虚设的节点。这样设计是为了满足C++标准库表示区间时左闭右开的惯例。

//接上例
Iter it = myList.end();
--it;
//C++11中可以直接写成it = prev(myList.end());
//这里prev是头文件<iterator>提供的函数，用于返回将某个迭代器前移一位的结果
Iter it2 = myList.insert(it, 3);
//myList的内容：1,3,2

这段代码首先定义了一个迭代器it，然后在end()的基础上左移一位，让它指向链表中最后一个元素。

insert(it, val)成员函数用于在链表中插入元素。it为该链表的一个迭代器，val为待插入的值，插入后val位于it所指位置的前一位。返回值为一个迭代器，表示val插入到了哪个位置。

//接上例
myList.remove(it);
//myList的内容：1,3
int x = *it + 10; //ERROR!

remove(it)成员函数用于删除某个迭代器所指的节点。注意在删除之后it就失效了，除非给it重新赋值，否则对它的任何操作都会导致错误！

除上述主要操作以外，list还提供了其他一些实用的成员函数：size()返回链表内元素的个数，empty()判断链表是否为空，remove(val)用于移除所有值为val的节点，以及作为成员函数的sort()和unique()。（注意sort(myList.begin(), myList.end())是错误的写法）

有了这些基础知识，我们就可以用STL来写本题了。代码如下：

#include <cstdio>
#include <list>

using namespace std;

using Iter = list<int>::iterator;

const int maxN = 1e5 + 10;
Iter pos[maxN];
list<int> queList;
bool erased[maxN];
int N;

void buildQueue()
{
    queList.push_front(1);
    pos[1] = queList.begin();

    for (int i = 2; i <= N; i++)
    {
        int k, p;
        scanf("%d%d", &k, &p);
        if (p == 0)
        {
            pos[i] = queList.insert(pos[k], i); //left
        }
        else
        {
            auto nextIter = next(pos[k]);
            pos[i] = queList.insert(nextIter, i); //right
        }
    }
    int M;
    scanf("%d", &M);
    for (int x, i = 1; i <= M; i++)
    {
        scanf("%d", &x);
        if (!erased[x])
        {
            queList.erase(pos[x]);
        }
        erased[x] = true;
    }
}

int main()
{
    scanf("%d", &N);
    buildQueue();
    bool first = true;
    for (int x: queList)
    {
        if (!first)
            putchar(' ');
        first = false;
        printf("%d", x);
    }
    putchar('\n');
    return 0;
}