我是靠谱客的博主 悲凉舞蹈,最近开发中收集的这篇文章主要介绍Team Queue(双端队列:deque),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题意

复制代码
1
2
3
4
5
有t个团队的人正在排一个长队。每次新来一个人时,如果他有队友在排队,那么这个新人会插队到最后一个队友身后。如果没有任何一个队友排队,则他会排到长队的队尾。输入每个团队中所有队员的编号,要求支持如下3种指令(前两种指令可以穿插进行)。 ENQUEUE:编号为X的人进入长队。 DEQUEUE:长队队首出队。 STOP:停止模拟。 对于每个DEQUEUE指令,输出出队的人的编号。

输入

复制代码
1
2
3
4
5
6
输入文件中有一组或多组测试数据。 每组测试数据开始有t个团队。下面t行,每行的第一个数字代表这个团队人数,后面是这几个人的编号。编号为0到999999之间的一个整数。 每组测试数据以“STOP”结束。 输入以t==0时结束。 警告:一个测试用例可能包含最多200000(二十万)个命令,所以实现 团队的队列应该是有效的。

输出

复制代码
1
对于每组测试数据,先打印一句"Scenario #k",k是第几组数据。对于每一个"DEQUEUE"指令,输出一个出队的人的编号。每组测试数据后要换行,即使是最后一组测试数据。

样例输入

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
2 3 101 102 103 3 201 202 203 ENQUEUE 101 ENQUEUE 201 ENQUEUE 102 ENQUEUE 202 ENQUEUE 103 ENQUEUE 203 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 2 5 259001 259002 259003 259004 259005 6 260001 260002 260003 260004 260005 260006 ENQUEUE 259001 ENQUEUE 260001 ENQUEUE 259002 ENQUEUE 259003 ENQUEUE 259004 ENQUEUE 259005 DEQUEUE DEQUEUE ENQUEUE 260002 ENQUEUE 260003 DEQUEUE DEQUEUE DEQUEUE DEQUEUE STOP 0

样例输出

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Scenario #1 101 102 103 201 202 203 Scenario #2 259001 259002 259003 259004 259005 260001

这个题题意是有t个队伍要排成一队,排队的规则是:如果当前正在排的总的队伍中有该人的队友则插入到队友后面的那个位置,否则站到队尾,根据这个特点,最终要出队时的每个状态(也就是当前排成的)总的队伍中原队伍的人一定是在一起的(每队组成一段连续的区间),这样只要根据原来每队中第一个人进入总队伍的顺序一队一队地输出就行了,其中每队的成员输出时按进入总队伍的顺序输出(先进先出),这样正好可以用双端队列实现。

双端队列:

复制代码
1
2
3
#include<deque> deque<int>dq;//定义一个int型的双端队列 双端队列的特点:队列的两端都可进行入队和出队操作

 

完整代码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h> #define int long long const int maxn=1e6+6; using namespace std; int t,n,vis[maxn];//vis[i]用来表示原队伍编号为i的队伍是否在总队伍中有人 deque<int>que[maxn];//que表示原来那t个队伍每次进队的人,que[i]根据进入总队伍的顺序依次保存第i个队伍中进入总队伍的人的编号 deque<int>teamque;//teamque表示那一个要排成的总的队伍(teamque中根据原来每队中第一个人进入总队伍的顺序依次保存原队编号) map<int,int>id;//id[i]表示编号为i的人所处的队伍编号 signed main() { ios::sync_with_stdio(false); cin.tie(0); int c=0; while(cin>>t&&t) { cout<<"Scenario #"<<++c<<endl; memset(vis,0,sizeof(vis)); for(int i=0;i<maxn;i++) que[i].clear(); teamque.clear(); id.clear(); for(int i=0;i<t;i++) { cin>>n; for(int j=0;j<n;j++) { int x; cin>>x; id[x]=i; } } string s; while(cin>>s&&s!="STOP") { if(s=="ENQUEUE"){ int x; cin>>x; if(!vis[id[x]]){ teamque.push_back(id[x]);//如果总队伍中没有该人的队友,就把这个人先放到teamque再放到que;否则直接放到que vis[id[x]]=1; } que[id[x]].push_back(x); } else{ int num=teamque.front();//出队时,从teamque中依次保存的编号为num的队伍开始输出 cout<<que[num].front()<<endl; que[num].pop_front(); if(que[num].empty()){ teamque.pop_front();//当当前队伍全都从总队伍出队后,让当前队伍编号从teamque中移除,然后继续让下一个队伍出队 vis[num]=0; } } } cout<<endl; } }

 

最后

以上就是悲凉舞蹈为你收集整理的Team Queue(双端队列:deque)的全部内容,希望文章能够帮你解决Team Queue(双端队列:deque)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(49)

评论列表共有 0 条评论

立即
投稿
返回
顶部