概述
小组队列
有n个小组要排成一个队列,每个小组中有若干人。
当一个人来到队列时,如果队列中已经有了自己小组的成员,他就直接插队排在自己小组成员的后面,否则就站在队伍的最后面。
请你编写一个程序,模拟这种小组队列。
输入格式:
输入将包含一个或多个测试用例。
对于每个测试用例,第一行输入团队数量t。
接下来t行,每行输入一个团队描述,每个团队描述由属于团队的元素数量和元素本身组成。
元素是0到999999范围内的整数。
一个团队最多可包含1000个元素。
最后,命令列表如下。 有三种不同的命令:
1、ENQUEUE x - 将元素x输入团队队列
2、DEQUEUE - 处理第一个元素并将其从队列中删除
3、STOP - 测试用例结束
每个命令占一行。
当输入用例t=0时,代表停止输入。
需注意:测试用例最多可包含200000(20万)个命令,因此团队队列的实现应该是高效的:
元素的入队和出队都应该只占用O(1)时间。
输出样例
对于每个测试用例,首先输出一行“Scenario #k”,其中k是测试用例的编号。
然后,对于每个DEQUEUE命令,输出出列的那个元素,每个元素占一行。
在每个测试用例(包括最后一个测试用例)输出完成后,输出一个空行。
数据范围
1≤t≤1000
这题挺好想的,单纯队列模拟
就是实现有些麻烦…
另外查找某个数属于的小组,某个小组是否在队中,一定要快
a[i]表示数字i所在小组
f[i]存小组i是否在队中,是的话存是第几个,不是为0
结构体
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 1005
#define MAXN 1000005
using namespace std;
int a[MAXN],f[N];
int h,t;
struct T
{
int h,t;
int m[N];
}q[N];//队列套队列 写的有点麻烦...
int main(){
//freopen("a.txt","r",stdin);
/*FILE *fp;
fp = freopen("a.txt","r",stdin);
if (fp == NULL)
cout<<"Open error!"<<endl;*/
int tt,k,ans=0;
string s;
while(cin>>tt && tt)
{
h=1,t=0;
ans++;
printf("Scenario #%dn",ans);
memset(f,0,sizeof(f));
for(int i=1;i<=N;++i)
{
q[i].h=1,q[i].t=0;
}
for(int i=1;i<=tt;++i)
{
cin>>k;
for(int j=1;j<=k;++j)
{
int d;
cin>>d;
a[d]=i;
}
}
while(cin>>s)
{
if(s=="ENQUEUE")
{
int d;
cin>>d;
if(f[a[d]])
{
q[f[a[d]]].t++;
q[f[a[d]]].m[q[f[a[d]]].t]=d;
}
else
{
t++;
q[t].t++;
q[t].m[q[t].t]=d;
f[a[d]]=t;
}
}
else if(s=="DEQUEUE")
{
cout<<q[h].m[q[h].h]<<endl;
q[h].h++;
if(q[h].h>q[h].t)
{
f[a[q[h].m[q[h].t]]]=0;//退了之后要清零 QAQ
h++;
}
}
else if(s=="STOP")
{
cout<<endl;
break;
}
/*cout<<h<<" "<<t<<endl;
for(int i=h;i<=t;++i)
{
cout<<i<<"# ";;
for(int j=q[i].h;j<=q[i].t;++j)
{
cout<<q[i].m[j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
}
}
return 0;
}
队列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int a[1000000];
queue<int> p,q[1005];
int main(){
//freopen("a.txt","r",stdin);
int n;
int ans=0;
while(scanf("%d",&n) && n)
{
ans++;
printf("Scenario #%dn",ans);
while(!p.empty())
{
p.pop();
}
for(int i=0;i<=1000;++i)
{
while(!q[i].empty())
{
q[i].pop();
}
}
for(int i=0;i<n;++i)
{
int k;
scanf("%d",&k);
for(int j=0;j<k;++j)
{
int d;
scanf("%d",&d);
a[d]=i;
}
}
string s;
while(1)
{
cin>>s;
if(s=="ENQUEUE")
{
int x;
scanf("%d",&x);
if(!q[a[x]].empty())
{
q[a[x]].push(x);
}
else
{
p.push(a[x]);
q[a[x]].push(x);
}
}
else if(s=="DEQUEUE")
{
int h=p.front();
printf("%dn",q[h].front());
q[h].pop();
if(q[h].empty())
{
p.pop();
}
}
else
{
printf("n");
break;
}
}
}
return 0;
}
最后
以上就是哭泣滑板为你收集整理的小组队列的全部内容,希望文章能够帮你解决小组队列所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复