题解 P2952 【[USACO09OPEN]牛线Cow Line】

Sooke · 2017-06-28 17:35:04 · 题解

楼上发的题解实在烦琐，这里教给大家一个 STL 的容器 deque，也就是高端的双向队列。

什么是双向队列？顾名思义，就是前面也可以进出，后面也可以进出的队列。本题中，序号不同的牛既可以从队列左边进出，也可以从队列左边进出，恰好可以用双向队列完美地解决。deque 的基本进入队列操作是 push_front 和 push_back，出队列操作是 pop_front 和 pop_back，都比原来的单向队列操作多了一些方向的描述。对于进入队列的牛的编号是多少，我们可以使用一个计数器变量 c，每进一头牛给它自增即可。

然而，deque 的时间复杂度可能比较高，平时练习队列的时候能手打最好避免使用，比赛时需要合理考虑时间复杂度酌情使用。

下面便是极短的代码：

#include <iostream>
#include <deque>
using namespace std;
deque < int > Q;
int main(){
    int n , c=1 , k;
    char a , b;
    cin >> n;
    for(int i=1 ; i <= n ; i++){
        cin >> a >> b;
        if(a == 'A' && b == 'L') Q.push_front(c++); else
        if(a == 'A') Q.push_back(c++);  else
        if(b == 'L'){
            cin >> k;
            for(int j=1 ; j <= k ; j++) Q.pop_front();
        } else {
            cin >> k;
            for(int j=1 ; j <= k ; j++) Q.pop_back();
        }
    }
    while(!Q.empty()) cout << Q.front() << endl , Q.pop_front();
    return 0;
}