题解：P1160 队列安排

ZTengW · 2026-01-07 13:04:26 · 题解

传送门。

思路

因为数据范围达到了 10^5，所以我们不使用普通的数组模拟，因为插入操作一定超时。
欸，那既然有插入操作，是不是证明可以用链表来做这道题呢？
是的。

链表有两种，一种是静态的，一种是动态的。这篇题解将使用静态链表。
这里定义第 i 个人的右边是 prev_i，左边是 next_i。
则我们插入的时候有两种情况：

• ```cpp a[i].prev=k; a[i].next=a[k].next; a[a[k].next].prev=i; a[k].next=i; ```
• ```cpp a[i].next=k; a[i].prev=a[k].prev; a[a[k].prev].next=i; a[k].prev=i; ```

我们再综合一下输入，就可以得到一份 AC 代码。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
struct node
{
    ll prev,next;
}a[N];
int main()
{
    ll n;
    scanf("%lld",&n);
    a[1].prev=-1,a[1].next=-1;
    for(ll i=2,k,p;i<=n;i++)
    {
        scanf("%lld%lld",&k,&p);
        if(p)
        {
            a[i].prev=k;
            a[i].next=a[k].next;
            a[a[k].next].prev=i;
            a[k].next=i;
        }
        else
        {
            a[i].next=k;
            a[i].prev=a[k].prev;
            a[a[k].prev].next=i;
            a[k].prev=i;
        }
    }
    ll m;
    scanf("%lld",&m);
    ll x;
    while(m--)
    {
        scanf("%lld",&x);
        if(a[x].prev==-1&&a[x].next==-1)
            continue;
        a[a[x].prev].next=a[x].next;
        a[a[x].next].prev=a[x].prev;
        a[x].next=a[x].prev=-1;
    }
    ll cur;
    for(ll i=1;i<=n;i++)
        if(a[i].prev>0||a[i].next>0)
        {
            cur=i;
            break;
        }
    while(a[cur].prev>0)
        cur=a[cur].prev;
    for(ll i=cur;i>0;i=a[i].next)
        printf("%lld ",i);
    return 0;
}

::::