【USACO Open 2009 Silver】 Cow Line

Problem here: Click here

題目內容

Farmer John’s N cows (conveniently numbered 1..N) are forming a line. The line begins with no cows and then, as time progresses, one by one, the cows join the line on the left or right side. Every once in a while, some number of cows on the left or right side of the line all leave the line to go graze in their favorite pasture.
FJ has trouble keeping track of all the cows in the line. Please help him.

The cows enter the line in numerical order 1..N, and once a cow leaves the line she never re-enters it. Your program will be given S (1 <= S <= 100,000) input specifications; each appears on a single line and is one of two types:

• A cow enters the line (a parameter indicates whether on the left or right).
• K cows leave the line from the left or right side (supplied parameters define both the number of cows and which side).

Input lines never request an operation that can not be performed.

After all the input lines have been processed, your program should print the cows in the line in order from left to right. The final line is guaranteed to be non-empty at the end of the input specifications.

執行限制

Time Limit: 1000ms

Memory Limit: 65536KB

這題用雙向鏈表(linkedlist)或列隊都可以做出來，但由於題目只需要在列隊的開頭和結尾進行操作，所以用deque就會比較方便

Solution

#include <iostream> #include <deque> #include <stdlib.h> #include <stdio.h>   using namespace std;   int main(){           int s;     while(cin >> s){         char lr, ad;         int num = -1;         deque<int> cows;         int count = 0;         while(s--){               cin >> ad;             if(ad == 'A'){                 count ++;                 cin >> lr;                 if(lr == 'L')                     cows.push_front(count);                 else if(lr == 'R')                     cows.push_back(count);                                   }else if(ad == 'D'){                 cin >> lr >> num;                 if(lr == 'L'){                     for(int i = 0; i < num; i++){                         cows.pop_front();                     }                 }else if(lr == 'R'){                     for(int i = 0; i < num; i++){                         cows.pop_back();                     }                                       }             }         }                     for(deque<int>::iterator alfa_it = cows.begin(); alfa_it != cows.end(); alfa_it++){             printf("%d\n", *alfa_it);         }           }           return 0; }

p.s. 用cout 來做輸出會出現TimeLimit 的情況，所以這裡還是乖乖的用printf吧