题解 P1160 【队列安排】

· · 题解

本蒟蒻第一篇题解

若有错误，请谅解

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

就没有然后了···

对于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<<" ";
    }

纯代码

#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;
}