题目

链接：https://ac.nowcoder.com/acm/contest/28537/L
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

ZZT 创造了一个队列 Q。这个队列包含了 N 个元素，队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素，QN 表示队尾元素。队列中的元素是 N 的一个全排列。

ZZT 需要在这个队列上执行 P 次操作，操作分两种：
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。

在 P 次操作之后，ZZT 想知道队列中的元素的排列方式，由于他最近很忙，因此需要请你帮他解决这个问题。

输入描述:
第一行输入一个正整数 N，表示队列的大小。

第二行输入 N 个正整数，Q1, Q2, Q3, ... ..., QN，Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。

第三行输入一个正整数 P，表示接下来要进行的操作次数。

接下来 P 行，第 i 行输入一个字符串 Si 以及一个正整数 Xi，表示一次操作。

1 ≤ N ≤ 105.

1 ≤ Qi ≤ N.

1 ≤ P ≤  105.

Si ∈\in∈ { “FIRST”, “LAST” }.

1 ≤ Xi ≤ 105.
输出描述:
输出 N 个正整数，表示 P 次操作之后的队列。
示例1

输入

[复制](javascript:void(0)
4

4 2 1 3

3

FIRST 4

LAST 2

LAST 1
输出

[复制](javascript:void(0)
4 3 2 1

题解

这道题目重点是快速地插入以及删除,这令我想到一个东西 list

但是,

list如果知道下标,那么他的访问速度相比于数组简直就是龟速

如果是搜索元素来的话,和数组一样都是龟速

这里并不知道下标,所以二者是龟速

这里我要写一个搜索引擎,

我明白:搜索引擎+list简直就是无敌

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-krzf6TuJ-1644552707980)(C:\Users\Lenovo\AppData\Roaming\Typora\typora-user-images\image-20220210195719550.png)]

不要害怕,为list建立索引,当list改变以后,索引仅仅需要修修补补,不要全部都换,因为地址没有改变!!!

代码

#include <iostream>

#include <list>

using namespace std;

list<int> ls;

list<int>::iterator search[1000009];

int main()

{

	int T;

	int n;

	cin >> n;

	for (int i = 0; i < n; i++)

	{

		auto tmp = ls.end();

		int buf;

		cin >> buf;

		ls.push_back(buf);

		tmp--;

		search[buf] = tmp;

	}

	cin >> T;

	while (T--)

	{

		int data;

		string s(12,0);

		cin >> s >> data;

		if (s == "FIRST")

		{

			ls.erase(search[data]);

			ls.push_front(data);

			search[data] = ls.begin();

		}

		else

		{

			ls.erase(search[data]);

			ls.push_back(data);

			auto tmp = ls.end();

			tmp--;

			search[data] = tmp;

		}

	}

	for (auto it = ls.begin(); it != ls.end(); it++)

		cout << *it << ' ';

	return 0;

}

然而出现了问题,但是我使用新学的暴力测试的方法解决了;-)

巴特西

队列Q_via牛客网

题目

题目描述

输入描述:

输出描述:

输入

输出

题解

代码

最新文章

热门文章