002. 队列安排(洛谷P1160)

题目描述

一个学校里老师要将班上 \(N\) 个同学排成一列，同学被编号为 \(1\sim N\)，他采取如下的方法：

1. 先将 \(1\) 号同学安排进队列，这时队列中只有他一个人；

2. \(2\sim N\) 号同学依次入列，编号为 \(i\) 的同学入列方式为：老师指定编号为 \(i\) 的同学站在编号为 \(1\sim(i-1)\) 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 \(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

4
1 0
2 1
1 0
2
3
3

样例输出 #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\)。

题解

解法一：

这道题是一道典型的模拟题，本人第一个想到的就是用数组（太年轻），然后每加一个同学，就把他后面的同学位置整体向后挪，将他放进去，然后

就没有然后了···

对于N，M ≤ 100000和这个无比粗暴的方法，不TLE就是奇迹

妄想偷懒不行，只能好好分析一下题

稍加观察可以看出，这是一个链式结构，移动同学肯定是不行的（时间复杂度太高），那么，只能对他们间的关系下手了

我们可以把每相邻的的两个同学想象成他们牵着手（如图） 既然如此，我们就只需要改动左右手指向的同学就可以了 定义一个结构体

struct T{
    int l,r;        //每个同学的“左右手” 
}t[mx]={0};

现在我们就手动模拟一下加入同学（以右边为例） 将编号为J的同学加入编号为i的同学右边

第一步 J的右手牵I右手牵的同学

t[j].r=t[i].r;

第二步 J的左手牵I

t[j].l=i;

第三步 I的右手牵J

t[i].r=j;

第四步 J右手牵的同学的左手牵J

注意：此时I的右手已经不牵原来那个同学了

t[t[j].r].l=j;

此时J就加入链当中了

左边同理

加入函数如下

void add(int i,int k,int f)       //新增同学 
{
    if(f==1)         //右 
    {
        t[k].r=t[i].r;
        t[k].l=i; 
        t[i].r=k;
        t[t[k].r].l=k;
    }
    else             //左
    {
        t[k].r=i;
        t[k].l=t[i].l;
        t[i].l=k;
        t[t[k].l].r=k;
    }
}

接下来是移除

我们虽然也可以用上面方法来删除

不过我用的是另一种方法（主要是懒）

我们可以给每个同学一个标记，标记了的将不会输出

struct T{
    int l,r;        //每个同学的“左右手” 
	int d;          //表示同学是否输出 
}t[mx]={0};

结构体

while(m--)
    {
        cin>>x;           //要删去的同学
        t[x].d=1;         //将该同学标记为不输出 
    }

标记

接下来是细节问题

链的初始化

如果我们将1同学先输入进去

t[1].l=1,t[1].r=1;

因为没有其他同学只能自己牵自己（紧紧抱住弱小的自己）

但如果这样，到输出时就有一个问题（以样例为例） 找不到开头！

这时我们就要在初始化时动些手脚

t[0].r=0,t[0].l=0;
    add(0,1,1);

定义个0同学 链将变成这样 我们只要从0的右手牵的同学开始输出，再到0结束就行了

输出代码

for (int i=t[0].r;i;i=t[i].r)
    {
        if (t[i].d==0)    //输出未标记的 
          cout<<i<<" ";
    }

AC代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx=1e5+10;
int n,m;
struct T{
    int l,r;        //每个同学的“左右手” 
	int d;          //表示同学是否输出 
}t[mx]={0};
void add(int i,int k,int f)       //新增同学 
{
    if(f==1)         //左 
    {
        t[k].r=t[i].r;
        t[k].l=i; 
        t[i].r=k;
        t[t[k].r].l=k;
    }
    else             //右 
    {
        t[k].r=i;
        t[k].l=t[i].l;
        t[i].l=k;
        t[t[k].l].r=k;
    }
}
int main()
{
    int x,k,f;
    cin>>n;
    t[0].r=0,t[0].l=0;
    add(0,1,1);
    for (int i=2;i<=n;i++)
    {
        cin>>x>>f;
        add(x,i,f);
    }
    cin>>m;
    while(m--)
    {
        cin>>x;
        t[x].d=1;         //将该同学标记为不输出 
    }
    for (int i=t[0].r;i;i=t[i].r)
    {
        if (t[i].d==0)    //输出未标记的 
          cout<<i<<" ";
    }
    return 0;
}

解法二：

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

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

list<int> myList;

这句代码声明了一个list类型的变量，也就是一个包含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::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;
}