直接用STL的的deque就好了...
----------------------------------------------------------------------
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<deque>
#define rep( i , n ) for( int i = 0 ; i < n ; i++ )
#define clr( x , c ) memset( x , c , sizeof( x ) )
using namespace std;
deque< int > Q;
int main() {
freopen( "test.in" , "r" , stdin );
int s , num = 0;
cin >> s;
rep( i , s ) {
char op , pos;
scanf( " %c %c" , &op , &pos );
if( op == 'A' ) {
pos == 'L' ? Q.push_front( ++num ) : Q.push_back( ++num );
} else {
int cnt;
scanf( "%d" , &cnt );
if( pos == 'L' ) {
while( cnt-- ) Q.pop_front();
} else {
while( cnt-- ) Q.pop_back();
}
}
}
while( ! Q.empty() ) {
printf( "%d\n" , Q.front() );
Q.pop_front();
}
return 0;
}
----------------------------------------------------------------------
3403: [Usaco2009 Open]Cow Line 直线上的牛
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 79 Solved: 70
[Submit][Status][Discuss]
Description
题目描述
约翰的N只奶牛（编为1到N号）正在直线上排队．直线上开始的时候一只牛也没有．接下来发生了S(1≤S≤100000)次事件，一次事件可能是以下四种情况之一：
．一只奶牛加入队伍的左边（输入“AL”）．
．一只奶牛加入队伍的右边（输入“AR”）．
·K只队伍左边奶牛离开（输入“DLK”）．
·K只队伍右边奶牛离开（输入“DRK”）．
请求出最后的队伍是什么样．
数据保证离开的奶牛不会超过队伍里的奶牛数，最后的队伍不空
Input
第1行输入S，之后S行每行描述一次事件，格式如题目描述所示
Output
由左到右输出队伍最后的情况．
Sample Input
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R
Sample Output
7
2
5
6
8
2
5
6
8