题解 | Cow Line-牛客假日团队赛9D题
D-Cow Line_牛客假日团队赛9
https://ac.nowcoder.com/acm/contest/1071/D
题目描述
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
* 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.
输入描述:
* Line 1: A single integer: S
* Lines 2..S+1: Line i+1 contains specification i in one of four formats:
* A L -- a cow arrives on the Left of the line
* A R -- a cow arrives on the Right of the line
* D L K -- K cows depart the Left side of the line
* D R K -- K cows depart the Right side of the line
输出描述:
* Lines 1..??: Print the numbers of the cows in the line in order from left to right, one number per line.
示例1
输入
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R
输出
7
2
5
6
8
说明
Input Resulting Cow Line
A L 1
A L 2 1
A R 2 1 3
A L 4 2 1 3
D R 2 4 2
A R 4 2 5
A R 4 2 5 6
D L 1 2 5 6
A L 7 2 5 6
A R 7 2 5 6 8
解答
这道题非常适合练习deque双端队列，~~既然是是练习的板子题了，建议大家还是练练deque，下面来简单讲解一下deque的一些操作。
)
：清空队列
)
：从尾部插入一个元素。
)
：从头部插入一个元素。
deque双端队列的先进就在这里，它可以两端都支持同样的操作。
... ......
... ......
... ......
然后输出的方法多种多样，我选择使用迭代器，具体详见代码。
代码：
#include<cstdio>
#include<deque>
using namespace std;
deque<int>q;
int main()
{
int s;
scanf("%d\n",&s);
int cnt=0;
for(int j=1;j<=s;j++)
{
char c1,c2;
int c3;
scanf("%c %c",&c1,&c2);
if(c1=='A')
{
if(c2=='L')
{
q.push_front(++cnt);
}
else
{
q.push_back(++cnt);
}
if(j!=s)
scanf("\n");
}
else
{
scanf("%d",&c3);
if(j!=s)
scanf("\n");
if(c2=='L')
{
for(int i=1;i<=c3;i++)
{
q.pop_front();
}
}
else
{
for(int i=1;i<=c3;i++)
q.pop_back();
}
}
}
deque<int>::iterator it=q.begin();
for(it=q.begin();it!=q.end();it++)
{
printf("%d\n",*it);
}
return 0;
} 来源：ShineEternal
查看13道真题和解析