首页 > 代码库 > HDU 4286 Data Handler --双端队列
HDU 4286 Data Handler --双端队列
题意：有一串数字，两个指针，然后一些添加，删除，反转，以及移动操作，最后输出序列。
解法：可以splay做，但是其实双端队列更简便。
维护三个双端队列LE,MI,RI分别表示[L,R]序列左边，[L,R]这段区间的值和[L,R]右边的值。然后维护一个revd标记表示[L,R]内的数是否被翻转了，翻转了的话改变一下一些操作就行了。自己写一个pop_Front()和pop_Back()函数，分别取队首和队尾元素，然后队首或队尾pop掉。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>using namespace std;#define N 500007deque<int> LE,MI,RI;deque<int>::iterator it;int fir,revd,a[N];int pop_Back(deque<int>& d){ int now = d.back(); d.pop_back(); return now;}int pop_Front(deque<int>& d){ int now = d.front(); d.pop_front(); return now;}void out(){ if(fir){ printf("%d",*it); fir = 0; } else printf(" %d",*it);}void print(){ fir = 1; for(it=LE.begin();it!=LE.end();it++) out(); if(revd) { for(it=MI.end()-1;it!=MI.begin()-1;it--) out(); } else { for(it=MI.begin();it!=MI.end();it++) out(); } for(it=RI.begin();it!=RI.end();it++) out(); puts("");}int main(){ int t,n,x,i,l,r,m; char ss1[15],ss2[3]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d%d%d",&l,&r,&m); LE.clear(), MI.clear(), RI.clear(); for(i=1;i<l;i++) LE.push_back(a[i]); for(i=l;i<=r;i++) MI.push_back(a[i]); for(i=r+1;i<=n;i++) RI.push_back(a[i]); revd = 0; while(m--) { scanf("%s",ss1); if(ss1[0] == ‘R‘) revd ^= 1; else if(ss1[0] == ‘M‘) { scanf("%s",ss2); if(ss1[4] == ‘L‘) //MoveLeft { if(ss2[0] == ‘L‘) //point L MoveLeft { x = pop_Back(LE); if(revd) MI.push_back(x); else MI.push_front(x); } else //point R MoveLeft { if(revd) x = pop_Front(MI); else x = pop_Back(MI); RI.push_front(x); } } else //MoveRight { if(ss2[0] == ‘L‘) //point L MoveRight { if(revd) x = pop_Back(MI); else x = pop_Front(MI); LE.push_back(x); } else //point R MoveRight { x = pop_Front(RI); if(revd) MI.push_front(x); else MI.push_back(x); } } } else if(ss1[0] == ‘I‘) { scanf("%s%d",ss2,&x); if(ss2[0] == ‘L‘) { if(revd) MI.push_back(x); else MI.push_front(x); } else { if(!revd) MI.push_back(x); else MI.push_front(x); } } else if(ss1[0] == ‘D‘) { scanf("%s",ss2); if(ss2[0] == ‘L‘) { if(revd) pop_Back(MI); else pop_Front(MI); } else { if(!revd) pop_Back(MI); else pop_Front(MI); } } } print(); } return 0;}
HDU 4286 Data Handler --双端队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。