P2952 [USACO09OPEN]牛线Cow Line

    • 914通过
    • 1.5K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 单调队列 模拟 递推 USACO 2009
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    约翰的N只奶牛(编为1到N号)正在直线上排队.直线上开始的时候一只牛也没有.接下来发生了S(1≤S≤100000)次事件,一次事件可能是以下四种情况之一:

    .一只奶牛加入队伍的左边(输入“AL”).

    .一只奶牛加入队伍的右边(输入“AR”).

    ·K只队伍左边奶牛离开(输入“DLK”).

    ·K只队伍右边奶牛离开(输入“DRK”).

    请求出最后的队伍是什么样.

    数据保证离开的奶牛不会超过队伍里的奶牛数,最后的队伍不空

    输入输出格式

    输入格式:

    * 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

    第1行输入S,之后S行每行描述一次事件,格式如题目描述所示

    输出格式:

    * 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 
    
    输出样例#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 提供翻译。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。