题意: 一个双端队列 ,可进行的操作:1.L x 在队列的左端插入x , 2.R x 在队列的右端插入x , 3.? x 查询min(x到最左端,x到最右端)
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2e5+10;
int Q[N];
int main()
{
int q,x;
char c;
scanf("%d",&q);
int l=0,r=-1;//双链表的初始化(l,r作为端点,中间放节点) 而此处把l,r作为中间点向左右扩展数字
while(q--)
{
cin>>c>>x;
if(c=='L') Q[x]=--l;// Q[x1]=-1,Q[x2]=-2
else if(c=='R') Q[x]=++r;// Q[y1]=1,Q[y2]=2
else
printf("%d\n",min(Q[x]-l,r-Q[x]));//Q[x],r,l都只是相对下标,求相对距离,不用加1哦~加1是求元素个数
}
return 0;
}
直接创建一个双端队列太复杂~~~(查询时不能弹出元素,即队列中的数字不会减少)
思想:很像桶排序(开一个数组 a[x]表示x出现的次数) ,此题是用数组存下标(位置),l一直更新为最左端的下标,r一直更新为最右端的下标,所以直接下标相减就是相对距离
数轴减:负数时,右边减左边->Q[x]-l ,这样才能得出正数,就不用绝对值函数了
中间下标设为什么数都可以,只是一个相对问题