队列安排
题目描述:一个学校里老师要将班上 N 个同学排成一列,同学被编号为 1∼N,他采取如下的方法:
(1)先将 1 号同学安排进队列,这时队列中只有他一个人;
(2)2∼N 号同学依次入列,编号为 i 的同学入列方式为:老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学(即之前已经入列的同学)的左边或右边;
(3)从队列中去掉 M 个同学,其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。
#include <bits/stdc++.h>
using namespace std;
#define N 100010
//left和right分别指向左右侧同学的下标。如果是-1则不存在
struct node
{
int left, right;
} x[N];
int main()
{
int n, m, k, p, d;
cin >> n;
//第一个同学进入队列
//x[0]作为头结点
x[0].right = 1;
x[1].left = 0;
x[1].right = -1;
for (int i = 2; i <= n; i++)
{
cin >> k >> p;//0左边,1右边
x[i].left = -1;
x[i].right = -1;
if (p == 0) //在左边插入
{
x[x[k].left].right = i;
x[i].left = x[k].left;
x[i].right = k;
x[k].left = i;
}
else if (p == 1) //在右边插入
{
x[i].right = x[k].right;
x[x[k].right].left = i;
x[k].right = i;
x[i].left = k;
}
}
/*
int j = x[0].right;
while (j != -1)
{
//cout << "(" << x[j].left << "," << j << "," << x[j].right << ') ';
cout << x[j].left << ':' << j << ":" << x[j].right << endl;
j = x[j].right;
}
cout << "-----------------------\n";
*/
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> d;
if (x[d].left == -1 && x[d].right == -1)
continue;
x[x[d].left].right = x[d].right;
x[x[d].right].left = x[d].left;
x[d].left = -1;
x[d].right = -1;
}
bool isfirst = true;
int j = x[0].right;
while (j != -1)
{
if (isfirst)
{
isfirst = false;
cout << j;
}
else
cout << ' ' << j;
j = x[j].right;
}
cout << endl;
return 0;
}
用结构体数组来模拟链表。
