AcWing 132 小组队列
发布日期:2021-05-28 16:31:39 浏览次数:9 分类:技术文章

本文共 2048 字,大约阅读时间需要 6 分钟。

题目描述:

有n个小组要排成一个队列,每个小组中有若干人。当一个人来到队列时,如果队列中已经有了自己小组的成员,他就直接插队排在自己小组成员的后面,否则就站在队伍的最后面。请你编写一个程序,模拟这种小组队列。

输入格式:

输入将包含一个或多个测试用例。对于每个测试用例,第一行输入小组数量t。接下来t行,每行输入一个小组描述,第一个数表示这个小组的人数,接下来的数表示这个小组的人的编号。编号是0到999999范围内的整数。一个小组最多可包含1000个人。

最后,命令列表如下。 有三种不同的命令:

1、ENQUEUE x - 将编号是x的人插入队列;

2、DEQUEUE - 让整个队列的第一个人出队;

3、STOP - 测试用例结束

每个命令占一行。当输入用例t=0时,代表停止输入。需注意:测试用例最多可包含200000(20万)个命令,因此小组队列的实现应该是高效的,入队和出队都需要使用常数时间。

输出样例

对于每个测试用例,首先输出一行“Scenario #k”,其中k是测试用例的编号。然后,对于每个DEQUEUE命令,输出出队的人的编号,每个编号占一行。在每个测试用例(包括最后一个测试用例)输出完成后,输出一个空行。

数据范围

1≤t≤1000

输入样例:

23 101 102 1033 201 202 203ENQUEUE 101ENQUEUE 201ENQUEUE 102ENQUEUE 202ENQUEUE 103ENQUEUE 203DEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25 259001 259002 259003 259004 2590056 260001 260002 260003 260004 260005 260006ENQUEUE 259001ENQUEUE 260001ENQUEUE 259002ENQUEUE 259003ENQUEUE 259004ENQUEUE 259005DEQUEUEDEQUEUEENQUEUE 260002ENQUEUE 260003DEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP0

输出样例:

Scenario #1101102103201202203Scenario #2259001259002259003259004259005260001

分析:

本题要求实现一个小组队列,具体做法是给每个小组维护一个队列,另外再维护一个总的队列。总队列里只需排各个小组的编号,一旦有人新加入队列,首先判断此前其小组队列是否为空,是则将小组的编号加入总队列,再将此人加入小组队列即可;若其小组队列不为空,则直接加入小组队列即可。执行出队操作时,首先从总队列里取得队头小组的编号,并且将该小组队列队头元素出队,出队后一旦该小组队列为空,则同时将该小组队列的编号从总队列中出队。

思路十分简单,唯一要注意的是入队时要快速判断此人属于哪个小组,采用哈希表可解决。因为任意一个人的编号在一百万以内,所以在读入各小组成员时就可以构建哈希映射,便于后续入队时在O(1)时间内找到小组队列。

#include 
#include
using namespace std;const int maxn = 1000005;int m[maxn];int main(){ ios::sync_with_stdio(false); int n; int cnt = 1; while(cin>>n,n){ cout<<"Scenario #"<
<
< n;i++){ cin>>nums; while(nums--){ cin>>x; m[x] = i; } } queue
total,person[n]; string s; while(cin>>s,s != "STOP"){ if(s == "ENQUEUE"){ cin>>x; int u = m[x]; if(person[u].empty()) total.push(u); person[u].push(x); } else{ int u = total.front(); cout<
<

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/89849432 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 133 蚯蚓
下一篇:AcWing 131 直方图中最大的矩形

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年01月24日 08时32分06秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

【ZJOI2014】BZOJ3527力题解(FFT) 2019-04-17
【SDOI2015】BZOJ3992 序列统计题解(DP+原根+NTT) 2019-04-17
【NOI2018】洛谷4770你的名字题解(SAM+线段树合并) 2019-04-17
BZOJ4025二分图题解(线段树分治+并查集) 2019-04-17
FJOI2019游记 2021-06-20
蓝书(算法竞赛进阶指南)刷题记录——POJ1011 Sticks(dfs+剪枝) 2021-06-20
蓝书(算法竞赛进阶指南)刷题记录——POJ3076 Sudoku(dfs+剪枝) 2021-06-20
蓝书(算法竞赛进阶指南)刷题记录——POJ2248 Addition Chains(迭代加深搜索+剪枝) 2021-06-20
ZJOI2019 Day2游记(爆0记) 2019-04-17
Codeforces 1155 D Beautiful Array 题解(DP) 2019-04-17
Codeforces 1152 D Neko and Aki's Prank 题解(记忆化搜索) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——POJ1475 Pushing Boxes(bfs套bfs) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——hdu3085 Nightmare2(双向bfs) 2019-04-17
分块入门1~9题解 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——CH5402 & 洛谷2014 选课(树形DP) 2019-04-17
Codeforces 1175 D Array Splitting 题解(DP+贪心) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——hdu2196 Computer(换根DP) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——POJ2888 Naptime(DP) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——Codeforces 24 D Broken Robot(概率期望+DP+高斯消元) 2019-04-17
蓝书(算法竞赛进阶指南)刷题记录——BZOJ2337【HNOI2011】XOR和路径(概率期望+DP+高斯消元) 2019-04-17