队列安排

作者: qiqi 分类: 经典案例 发布时间: 2025-10-14 18:57

提交链接

题目描述:一个学校里老师要将班上 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;
}

用结构体数组来模拟链表。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

标签云