book pile SGU

有n本书从上到下摞在一起，有两种操作。ADD(C)表示把一本新书C放到这一摞书的最顶上，ROTATE表示将前K本书进行反转。在一系列操作后输出最后书的顺序

分析：

当时听别人讲这个题的时候很懵逼，后来自己读了一下题发现K是个固定的值，这样就好解决了

每次反转操作只是针对于顶上的K个进行。

我们可以用一个两个双端队列解决

第一个双端队列储存前K本书，第二个双端队列（也可以是别的栈或者普通队列什么的因为不会再进行反转了）储存剩下的书。

对于每个反转操作，只需要将双端队列的头和尾交换一下（并不是真的交换，用一个标记记录一下就可以了）

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <map>

 #include <queue>

 using namespace std;

 const int maxn=+;

 string Name[maxn];

 deque<int>q1,q2;

 int front1,front2;//1正常0交换

 int n,m,k;

 int main(){

     scanf("%d%d%d",&n,&m,&k);

     string s;

     for(int i=;i<=n;i++){

         cin>>s;

         Name[i]=s;

         q1.push_back(i);

     }

     front1=front2=;

     for(int i=;i<=n-k;i++){

         q2.push_front(q1.back());

         q1.pop_back();

     }

     for(int i=;i<=m;i++){

         cin>>s;

         if(s=="ROTATE")front1=!front1;

         else{

             string NAME;

             bool judge=;

             for(int j=;j<s.length();j++){

                 if(s[j]=='('){judge=;continue;}

                 if(s[j]==')'){judge=;break;}

                 if(judge)NAME+=s[j];

             }

             ++n;

             Name[n]=NAME;

             if(front1){

             q1.push_front(n);

             if(q1.size()>k){

             q2.push_front(q1.back());

             q1.pop_back();

             }

             }else{

                 q1.push_back(n);

                 if(q1.size()>k){

                 q2.push_front(q1.front());

                 q1.pop_front();

                 }

             }

         }

     }

     while(!q1.empty()){

         int u;

         if(front1){

          u=q1.front();q1.pop_front();

         }

         else{

          u=q1.back();q1.pop_back();

         }

         cout<<Name[u]<<endl;

     }

     while(!q2.empty()){

         int u=q2.front();q2.pop_front();

         cout<<Name[u]<<endl;

     }

 return ;

 }

巴特西

book pile SGU - 271

最新文章

热门文章