Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024
Main » 2013 » August » 23 » [noip]奶牛线条
11:07 AM
[noip]奶牛线条

prob.

 [NOIP2011模拟赛_No.2]牛的线条

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 74  Solved: 53
[Submit][Status][Web Board]

Description

Farmer John有N只奶牛（标号为1--N）正在排队，一开始队伍中一只奶牛都没有，然后奶牛可以选择从左边排进去或者从右边排进去。每过一小会，有些在队伍两端的奶牛会选择离开队伍去吃草。
FJ现在陷入怎么让奶牛排好队的苦恼，你来帮帮他！
一开始奶牛先按照1—N的次序准备好，奶牛一旦离开队列后就再也不会回来了，你的问题是给你S（1<=S<=100,000）个输入，每个输入一行，每行有两种类型：
     A轮到的奶牛去排队（从左边或者右边）
     K 有K只奶牛从左边或者右边离开队列
      善良的LiJian保证输入都是合法的。
      所有的输入完成后，你的程序需要按照从左到右的顺序打印出还在那里安心排队的奶牛，每只奶牛一行！

Input

第1行：S
第2..S+1行
      A L 从左边进入排队
      A R 从右边进入排队
      D L K 有K只奶牛从左边离开
      D R K 有K只奶牛从右边离开

Output

第1..？行，每行一只奶牛，表示最后还在排队的奶牛。

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

Sample Output

7 2 5 6 8

HINT

Source

code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define N 200010
using namespace std;
int n,i,q[N],k;
int main()
{
  ios::sync_with_stdio(false);
  cin>>n;
  int pl=100000,pr=100001;
  char c1,c2;
  int count=0;
  for (i=1;i<=n;i++)
  {
    cin>>c1>>c2;
    if (c1=='A')
    {
      if (c2=='L') 
      {
        count++;
        q[pl]=count;
        pl--;
      }else
      {
        count++;
        q[pr]=count;
        pr++;
      }
    }else 
    {
      cin>>k;
      if (c2=='L') pl+=k;else pr-=k;
    }
  }
  for (i=pl+1;i<=pr-1;i++) printf("%d\n",q[i]);
} 

Views: 430 | Added by: dhy0077 | Rating: 5.0/1
Total comments: 0
Only registered users can add comments.
[ Sign Up | Login ]