题目描述
给定一个双端队列,初始时队列为空。
你要对其进行 q 次操作,每次操作可能是以下三种之一:
1.L x,从队列的左端插入整数 x。
2.R x,从队列的右端插入整数 x。
3.? x,请你计算为了使已经处于队列中的整数 x 位于队列的最左端或最右端,至少需要从最左端或最右端弹出多少个数字。
保证操作 3 一定合法( ? x 中的 x 一定已经处于队列之中)。
每个数字最多被插入到队列中 1 次(队列中一定不会存在重复数字)。
注意,操作 3 只是询问最少需要弹出多少数字,不是真的要弹出它们,队列中的数字始终不会减少。
样例
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
算法1
直接映射x的下标 单次查询时间复杂度 $O(1)$
比赛的时候突然想到的
插入从中间开始即可,重点是查询
往左边插就是在数组左边加一个数字,右边插就是在右边加一个数字,x各不相同
那么建立一个映射表,直接记录x的位置在哪,算一下x左右端距离最小值即可
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 200010;
int v[N];
int hd, tl;
int q;
int pos[N];
void insertl(int u)
{
v[--hd] = u;
pos[u] = hd;
}
void insertr(int u)
{
v[++tl] = u;
pos[u] = tl;
}
int query(int x)
{
return min(abs(pos[x] - hd), abs(pos[x] - tl));
}
int main()
{
hd = 1e5+5, tl = hd-1;
char op[2]; int x;
scanf("%d", &q);
while(q --)
{
scanf("%s%d", op, &x);
if(op[0] == 'L')
{
insertl(x);
}
else if(op[0] == 'R')
{
insertr(x);
}
else
{
cout << query(x) << endl;
}
}
return 0;
}