SGU 271 Book Pile（双端队列） - c++编程基础

271. Book Pile

time limit per test: 0.25 sec.
memory limit per test: 65536 KB input: standard
output: standard

There is a pile of N books on the table. Two types of operations are performed over this pile:
- a book is added to the top of the pile,
- top K books are rotated. If there are less than K books on the table, the whole pile is rotated.
First operation is denoted as ADD(S) where S is the name of the book, and the second operations is denoted as ROTATE.
The maximum number of books is no more than 40000. All book names are non-empty sequences of no more than 3 capital Latin letters. The names of the books can be non-unique.
Input The first line of input file contains 3 integer numbers N, M, K (0 <= N <= 40000; 0 <= M <= 100000; 0 <= K <= 40000). The following N lines are the names of the books in the pile before performing any operations. The book names are given in order from top book to bottom. Each of the following M lines contains the operation description.

Output Output the sequence of books names in the pile after performing all operations. First line corresponds to the top book.

Sample test(s)
Input

2 3 2 A B ADD(C) ROTATE ADD(D) Output

D
A
C
B
题意：一开始桌子上从上到下放着N本书（N <= 40000），有M组操作：1.将前K本书翻转，2.在头上加一本书。最后输出书的顺序。思路：只要维护前K本书即可。用双端队列维护，翻转时，只要改变双端队列的头的方向即可。多出来的书添加到另一个双端队列中。需要特别注意当k=0的时候的情况，容易RE，以及输入输出不要用string。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             using namespace std; typedef long long LL; #define REP(_,a,b) for(int _ = (a); _ <= (b); _++) int n,m,k; int dir; deque
            
              ds; deque
             
               extra; void init() { ds.clear(); extra.clear(); dir = 1; } void input() { string a; char st[10]; REP(i,1,n) { scanf("%s",st); if(i > k) { extra.push_back(string(st)); }else{ ds.push_back(string(st)); } } } string getName(char *opt) { string name; bool flag = false; int len = strlen(opt)-1; REP(i,0,len) { if(opt[i]==')') { flag = false; } if(flag) name += opt[i]; if(opt[i]=='(') { flag = true; } } return name; } void Add(string st) { if(ds.size() == k) { if(dir) { string t = ds.back(); ds.pop_back(); extra.push_front(t); ds.push_front(st); }else{ string t = ds.front(); ds.pop_front(); extra.push_front(t); ds.push_back(st); } }else{ if(dir) { ds.push_front(st); }else{ ds.push_back(st); } } } void Rotate() { dir = 1-dir; } void solve() { char st[100]; while(m--) { scanf("%s",st); if(st[0]=='A') { string name = getName(st); if(k==0) { extra.push_front(name); }else{ Add(name); } }else if(k!=0){ Rotate(); } } if(!dir) reverse(ds.begin(),ds.end()); for(deque
              
               ::iterator it = ds.begin(); it != ds.end(); it++) { printf("%s\n",(*it).c_str()); } for(deque
               
                ::iterator it = extra.begin(); it != extra.end(); it++) { printf("%s\n",(*it).c_str()); } } int main(){ while(~scanf("%d%d%d",&n,&m,&k)) { init(); input(); solve(); } return 0; }