[USACO09OPEN] Cow Line S
题面翻译
Farmer John（以下简称 FJ）的 N N N 头奶牛（用 1 … N 1 \dots N 1…N 编号）在直线上排队。一开始，这条线上没有任何奶牛，随着时间的推移，奶牛们会一个接一个地站到队伍的左边或右边。又过了一会儿，某些奶牛会从队伍里离开，去吃自己最喜欢的草料。
FJ 无法跟踪每一头奶牛，于是，他想让你来帮助他。
奶牛以 1 … N 1 \dots N 1…N 的顺序排队，并且离开的奶牛不会再次回来。数据将会给出 S S S（ 1 ≤ S ≤ 100000 1 \le S \le 100000 1≤S≤100000） 条指令，各占一行，分两种：
- A A A 头奶牛加入了队列（还有一个参数，表示从左加入还是从右加入）；
- K K K 头奶牛从左边或者右边离开了队列（还有两个参数，分别表示从左离开还是从右离开和离开多少头奶牛）。
输入的命令一定是可以执行的。
所有的操作结束后，你的程序应该以从左到右的顺序输出这个奶牛队列。数据保证最后的队列不空。
【输入格式】
- 第 1 1 1 行：单独一个整数 S S S。
- 第
2
…
S
+
1
2 \dots S+1
2…S+1 行：第
i
+
1
i+1
i+1 行会有一条命令，有以下几种：
A L：一头奶牛从队列左边加入；A R：一头奶牛从队列右边加入；D L K： K K K 头奶牛从队伍左边离开；D R K： K K K 头奶牛从队伍右边离开。
【输出格式】
- 第 1 … ? ? 1 \dots ?? 1…?? 行：从左到右输出最后的奶牛队列，一个奶牛编号占一行。
【样例解释】
以下为输入的命令及对应的队列：
A L： 1 1 1；A L： 2 , 1 2,1 2,1；A R： 2 , 1 , 3 2,1,3 2,1,3；A L： 4 , 2 , 1 , 3 4,2,1,3 4,2,1,3；D R 2： 4 , 2 4,2 4,2；A R： 4 , 2 , 5 4,2,5 4,2,5；A R： 4 , 2 , 5 , 6 4,2,5,6 4,2,5,6；D L 1： 2 , 5 , 6 2,5,6 2,5,6；A L： 7 , 2 , 5 , 6 7,2,5,6 7,2,5,6；A R（最终序列）： 7 , 2 , 5 , 6 , 8 7,2,5,6,8 7,2,5,6,8。
题目描述
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.
输入格式
* 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
样例输入 #1
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R
样例输出 #1
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
感谢@ ws_fuweidong 提供翻译。
代码
#include <iostream>
using namespace std;
const int N = 100010;
int l[N],r[N],e[N], idx;
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
//在第k个数字的右边加上一个奶牛
void add(int k)
{
e[idx] = idx - 1;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
//将第k个插入的数字删除
void left(int k)
{
l[r[k]] = l[k];
r[l[k]] = r[k];
}
int main()
{
init();
int s; cin >> s;
while (s--)
{
char x,y;
int z;
cin >> x;
if (x == 'A')
{
cin >> y;
//一头奶牛从队列左边加入
if (y == 'L') add(0);
else add(l[1]);//一头奶牛从队列右边加入
}
else if (x == 'D')
{
cin >> y >> z;
if (y == 'L')
{
for( int i = 0;i < z;i++)
left(r[0]);//K 头奶牛从队伍左边离开
}
else {
for (int i = 0; i < z; i++)
left(l[1]);
}
}
}
for (int i = r[0]; i != 1; i = r[i])
cout << e[i] << "\n";
return 0;
}