有n本书从上到下摞在一起,有两种操作。ADD(C)表示把一本新书C放到这一摞书的最顶上,ROTATE表示将前K本书进行反转。在一系列操作后输出最后书的顺序
分析:
当时听别人讲这个题的时候很懵逼,后来自己读了一下题发现K是个固定的值,这样就好解决了
每次反转操作只是针对于顶上的K个进行。
我们可以用一个两个双端队列解决
第一个双端队列储存前K本书,第二个双端队列(也可以是别的栈或者普通队列什么的因为不会再进行反转了)储存剩下的书。
对于每个反转操作,只需要将双端队列的头和尾交换一下(并不是真的交换,用一个标记记录一下就可以了)
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <iostream> 5 #include <map> 6 #include <queue> 7 8 using namespace std; 9 const int maxn=40000+10; 10 string Name[maxn]; 11 deque<int>q1,q2; 12 int front1,front2;//1正常0交换 13 int n,m,k; 14 int main(){ 15 scanf("%d%d%d",&n,&m,&k); 16 string s; 17 for(int i=1;i<=n;i++){ 18 cin>>s; 19 Name[i]=s; 20 q1.push_back(i); 21 } 22 front1=front2=1; 23 for(int i=1;i<=n-k;i++){ 24 q2.push_front(q1.back()); 25 q1.pop_back(); 26 } 27 for(int i=1;i<=m;i++){ 28 cin>>s; 29 if(s=="ROTATE")front1=!front1; 30 else{ 31 string NAME; 32 bool judge=0; 33 for(int j=0;j<s.length();j++){ 34 if(s[j]=='('){judge=1;continue;} 35 if(s[j]==')'){judge=0;break;} 36 if(judge)NAME+=s[j]; 37 } 38 ++n; 39 Name[n]=NAME; 40 if(front1){ 41 q1.push_front(n); 42 if(q1.size()>k){ 43 q2.push_front(q1.back()); 44 q1.pop_back(); 45 } 46 }else{ 47 q1.push_back(n); 48 if(q1.size()>k){ 49 q2.push_front(q1.front()); 50 q1.pop_front(); 51 } 52 } 53 54 } 55 } 56 while(!q1.empty()){ 57 int u; 58 if(front1){ 59 u=q1.front();q1.pop_front(); 60 } 61 else{ 62 u=q1.back();q1.pop_back(); 63 } 64 cout<<Name[u]<<endl; 65 } 66 while(!q2.empty()){ 67 int u=q2.front();q2.pop_front(); 68 cout<<Name[u]<<endl; 69 } 70 return 0; 71 }