题目链接
题目大意
进行四种操作
L在队列左端插入
R在右插入
Q询问当前队列中间数字
G取出某个数字
其中插入数字的顺序是++num
题目思路
用两个双端队列模拟
插入L就进入L的左边
插入R就进入R的右边
每次输出R的最左边
对于要删除的数字进行标记
每次操作后平衡两个 队列
如果L数量大于R
就push L_back到R_front
反之亦然
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
deque<int >l,r;
int del[maxn];
int typ[maxn];
int q;
int lsz,rsz;
char c;
int num=0;
int main()
{cin>>q;getchar();while(q--){scanf("%c",&c);getchar();if(c=='L'){l.push_front(++num);typ[num]=0;lsz++;}else if(c=='R'){r.push_back(++num);typ[num]=1;rsz++;}else if(c=='G'){int t;scanf("%d",&t);getchar();if(typ[t])rsz--;else lsz--;del[t]=1;}else {while(del[r.front()])r.pop_front();printf("%d\n",r.front());}//平衡 if(lsz>rsz){while(del[l.back()])l.pop_back();r.push_front(l.back());l.pop_back();typ[r.front()]^=1;lsz--;rsz++;}else if(rsz>lsz+1){while(del[r.front()])r.pop_front();l.push_back(r.front());r.pop_front();typ[l.back()]^=1;lsz++;rsz--;}}return 0;
}