| 题目名称 | 762. [USACO Open09] 奶牛队列 |
|---|---|
| 输入输出 | cline.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-04-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：120， 提交：177， 通过率：67.8% | ||||
 Hzoi_chairman |
100 | 0.000 s | 0.00 MiB | C++ |
 金身人面兽 |
100 | 0.000 s | 0.00 MiB | C++ |
 Go灬Fire |
100 | 0.000 s | 0.00 MiB | C++ |
|
Hzoi_Go灬Fire |
100 | 0.000 s | 0.10 MiB | C++ |
 new ioer |
100 | 0.015 s | 2.77 MiB | C++ |
 rushcheyo |
100 | 0.017 s | 65.05 MiB | C++ |
|
rushcheyo |
100 | 0.020 s | 65.05 MiB | C++ |
|
rushcheyo |
100 | 0.022 s | 1.85 MiB | C++ |
|
rushcheyo |
100 | 0.027 s | 2.05 MiB | C++ |
|
rushcheyo |
100 | 0.030 s | 58.55 MiB | C++ |
| 本题关联比赛 | |||
| 20120416 | |||
| 关于 奶牛队列 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
qnq看来只有我写平衡树？
| ||||
|
COGS 居然不让用 mmap，让卡常大军退散。
rushcheyo
2016-09-15 13:53
15楼
| ||||
|
new ioer 跟我代码差不多，我还少了一个循环，我们都写了fread，怎么我刷了几十次还刷不到rank1？
rushcheyo
2016-09-15 13:44
14楼
| ||||
|
手写双向队列真慢！
| ||||
|
蛋疼的我用了deque。。。
 O(1)
2015-12-17 18:02
12楼
| ||||
|
这道题直接开个数组，以中间为基准，向两端扩张和收缩就行了，其实用不着STL和手写双向链表的。。。
| ||||
|
。。。
 NOI_killer
2015-09-29 20:31
10楼
| ||||
|
双端链表而已= =大家都好懒
| ||||
|
STL无限好OvO..
| ||||
|
stl就是福利一样的存在，但楼上居然手写…
| ||||
sxysxy
Satoshi
琴殇''遙暩焱鐄
筽邝
水中音【题目描述】
农夫约翰有$n$头牛，编号依次为$1\sim n$，他正在把这些牛排成一队，队伍中开始是没有牛的，随着时间推移，牛儿一个一个地从左端或右端加入到队伍中来。令人烦心的是，随时会有一些牛从左端或右端离开队伍溜向草场。
FJ正费劲地给牛排队，请你帮帮他。
奶牛按$1\sim n$的顺序入队，牛一旦离队就再也不会回来了，你的程序将处理给定的$s(1\leq s\leq 10^5)$个输入指令，每一个指令占一行，指令有两种类型：
1、一头牛入队（带有一个参数，代表从左端入队还是右端入队）
2、$k$头牛从左端或右端离队（提供的参数包括离队牛数及是从哪端离队）
输入指令中没有提到的操作则不会被执行。
当所有的输入指令都执行完毕后，你的程序必须要按从左到右的顺序输出队伍中牛的编号，最后的队伍保证不为空。
【输入格式】
第一行一个整数$s$，表示指令的数量。
接下来$s$行，每行一个指令，指令有4种格式：
A L，表示有一头牛从左端入队；
A R，表示有一头牛从右端入队；
D L k，表示有$k$头牛从队伍左端离队；
D R k，表示有$k$头牛从队伍右端离队。
【输出格式】
输出包含若干行，表示所有操作完成后，队列中牛的编号，按照从左到右的顺序输出队伍中牛的编号，一个数一行。
【输入样例】
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
【输入输出样例解释】
指令 执行完指令后牛的队伍
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