队列Q

第一行输入一个正整数 N，表示队列的大小。
第二行输入 N 个正整数，Q₁, Q₂, Q₃, ... ..., Q_N，Q_i 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。
第三行输入一个正整数 P，表示接下来要进行的操作次数。

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

1 ≤ N ≤ 10⁵.
1 ≤ Q_i ≤ N.
1 ≤ P ≤ 10⁵.
S_i{ “FIRST”, “LAST” }.
1 ≤ X_i ≤ 10⁵.

C++ 解法, 执行用时: 89ms, 内存消耗: 1784K, 提交时间: 2022-05-30 09:10:00

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],p[N];
bool cmp(int a,int b){
	return p[a]<p[b];
}
int main(){
	int n,m,x;
	string op;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[a[i]]=i;
	}
	cin>>m;
	int l=0,r=n+1;
	while(m--){
		cin>>op>>x;
		if(op=="FIRST"){
			p[x]=l--;
		}
		else{
			p[x]=r++;
		}
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	cout<<a[i]<<' ';
	
}

Python3(3.5.2) 解法, 执行用时: 631ms, 内存消耗: 42724K, 提交时间: 2018-07-06 19:14:43

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = [input().split() for i in range(m)]
c = [0] * n
d = [0] * n
l, r = 0, -1
for e in b[::-1]:
	if d[int(e[1]) - 1]:
		continue
	else:
		d[int(e[1]) - 1] = 1
		if e[0] == 'FIRST':
			c[l] = int(e[1])
			l += 1
		else:
			c[r] = int(e[1])
			r -= 1
for i in range(n):
	if d[a[i] - 1] == 0:
		c[l] = a[i]
		l += 1
print(*c)

详情