CodeForces - 1066C Books Queries(思维)

题目链接：点击查看

题目大意：给出n次操作，每次操作分为以下三种：(假设现在有一个空的队列)

L x，在最左端插入x

R x，在最右端插入x

? x，查询若想要让x到达最右端或最左端，最少需要移除掉几个数

对于每个查询，输出相应的答案

题目分析：这个题目一开始我想从右端维护一个map，再从左端维护一个map，但是在查询的时候遇到了一个小问题就是加入x是从左边插入的，但是从右边移除是最优解，这个时候不能输出正确答案，想了半天没有什么思路，去网上看了一下题解才发现，因为答案要我们求的是相对位置，我们只需要动态维护两个指针l和r表示区间长度，然后用一个map维护区间内的位置即可，每次插入操作相应的赋值，并且扩展区间就可以了。。看过代码之后真的觉得自己的思维总是差点火候，不多说了，直接看代码吧

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;unordered_map<int,int>mp;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);int l=0,r=-1;//初始的区间是[0,-1]，表示的是一个元素都不存在的区间while(n--){char s[5];int x;scanf("%s%d",s,&x);if(s[0]=='L')mp[x]=--l;else if(s[0]=='R')mp[x]=++r;elseprintf("%d\n",min(r-mp[x],mp[x]-l));}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1066C Books Queries(思维)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。