首页 > 代码库 > cogs 762. [USACO Open09] 奶牛队列

cogs 762. [USACO Open09] 奶牛队列

2024-10-14 01:04:39   215人阅读

★   输入文件：cline.in   输出文件：cline.out   简单对比
时间限制：1 s   内存限制：128 MB

农夫约翰有N头牛，编号依次为1～N，他正在把这些牛排成一队，队伍中开始是没有牛的，随着时间推移，牛儿一个一个地从左端或右端加入到队伍中来。令人烦心的是，随时会有一些牛从左端或右端离开队伍溜向草场。

FJ正费劲地给牛排队，请你帮帮他。

奶牛按1～N的顺序入队，牛一旦离队就再也不会回来了，你的程序将处理给定的S(1 <= S <= 100,000)个输入指令，每一个指令占一行，指令有两种类型：

*一头牛入队（带有一个参数，代表从左端入队还是右端入队）
*K头牛从左端或右端离队（提供的参数包括离队牛数及是从哪端离队）

输入指令中没有提到的操作则不会被执行。

当所有的输入指令都执行完毕后，你的程序必须要按从左到右的顺序输出队伍中牛的编号，最后的队伍保证不为空。


输入格式：
第1行：一个整数S；
第2～S+1行：第i+1行写着一个指令，指令有4种格式：
*A L ——表示有一头牛从左端入队；
*A R ——表示有一头牛从右端入队；
*D L K ——表示有K头牛从队伍左端离队；
*D R K ——表示有K头牛从队伍右端离队；

输出格式：
第1～？？行：按从左到右的顺序输出队伍中牛的编号，一个数一行。

输入输出样例：
cline.in
10
A L
A L
A R
A L
D R 2
A R
A R
D L 1
A L
A R

cline.out
7
2
5
6
8

输出样例解释：
指令   执行完指令后牛的队伍
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

 

//初始设一个很大的数，从中间向两边扩展 
#include<iostream> 
#include<cstdio>
#define N 100010
using namespace std;

int q;
int f[N]={0};
void work()
{
    int i,j,k,l,r,num,tot=0,L;
    char op,ha;
    l=50000;
    r=49999;
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>op;
        if(op==‘A‘)
        {
            cin>>ha;
            tot++;
            if(ha==‘R‘)f[++r]=tot;
            if(ha==‘L‘)f[--l]=tot;
        }
        else
        {
            cin>>ha>>num;
            L=r-l+1;
            if(num>=L)l=r;
            else
            {
                if(ha==‘L‘)l+=num;
                else r-=num;
            }
        }
        
    }
    for(k=l;k<=r;k++)cout<<f[k]<<endl;
}
int main()
{
    freopen("cline.in","r",stdin);
    freopen("cline.out","w",stdout);
    work();
    return 0;
}

 

cogs 762. [USACO Open09] 奶牛队列


联系
我们