540 - Team Queue

68 阅读 0 评论 45 点赞

我是靠谱客的博主唠叨飞鸟，最近开发中收集的这篇文章主要介绍540 - Team Queue，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目的意思就是排队买票问题，就像好多班在买票，前面如果有和自己买票的就可以插队，但是只能插到自己班的最后一名，如果没有自己班的排队买票就只能在所有人后面慢慢排队买票了，我采用了栈以及数组和链表，但是一般不要用stl，要不然很容易超时，第一次提交时完全用的stl所以超时了……下面是代码
 
第一次提交的代码，但是超时了……
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <list>
#include <vector>
#include <algorithm>
usingnamespacestd;
typedefqueue<int> q;
typedeflist<int> l;
intmain()
{
//freopen("a.txt","r",stdin);
intn,c(1);
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
else
{
printf("Scenario #%dn",c);
vector<l> v;
v.clear();
intm,x;
while(n--)
{
scanf("%d",&m);
l list1;
list1.clear();
while(m--)
{
scanf("%d",&x);
list1.push_back(x);
}
v.push_back(list1);
}
list<q> qu;
list<q>::iterator p;
qu.clear();
list<int> count;
list<int>::iterator i;
count.clear();
intflag(0);
chars[10];
memset(s,0,sizeof(s));
while(scanf("%s",s)!=EOF)
{
if(strcmp(s,"STOP")==0)break;
elseif(strcmp(s,"ENQUEUE")==0)
{
scanf("%d",&m);
flag++;
for(x=0; x<v.size(); x++)
{
i=find(v[x].begin(),v[x].end(),m);
if(i!=v[x].end())break;
}
if(flag>=2)
{
for(i=count.begin(),p=qu.begin(); i!=count.end(); p++, i++)
if(*i==x)break;
}
elsei=count.end();
if(i==count.end())
{
count.push_back(x);
q queue1;
queue1.push(m);
qu.push_back(queue1);
}
else
{
(*p).push(m);
flag--;
}
}
elseif(strcmp(s,"DEQUEUE")==0)
{
printf("%dn",qu.front().front());
qu.front().pop();
if(qu.front().size()==0)
{
qu.pop_front();
count.pop_front();
}
}
memset(s,0,sizeof(s));
}
printf("n");
}
c++;
}
return0;
}
第二次提交代码（没有超时，ac了）：
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <list>
#include <vector>
#include <algorithm>
usingnamespacestd;
longstr[1010][1010];
typedefqueue<long> q;
intmain()
{
//freopen("a.txt","r",stdin);
longn,cx(1);
while(scanf("%ld",&n)!=EOF)
{
memset(str,0,sizeof(str));
if(n==0)break;
else
{
printf("Scenario #%ldn",cx);
longm,i(0),j,c,maxn(0);
while(i<n)
{
scanf("%ld",&m);
j=0;
while(j<m)
{
scanf("%ld",&c);
str[i][j++]=c;
}
i++;
if(maxn<m)maxn=m;
}
list<q> l;
list<q>::iterator p;
l.clear();
list<long> count;
list<long>::iterator k;
count.clear();
chars[10];
memset(s,0,sizeof(s));
while(scanf("%s",s)!=EOF)
{
intflag(0);
if(strcmp(s,"STOP")==0)break;
elseif(strcmp(s,"ENQUEUE")==0)
{
scanf("%ld",&c);
for(i=0; i<n; i++)
{
for(j=0; str[i][j]&&j<maxn; j++)
if(c==str[i][j])
{
flag=1;
break;
}
if(flag==1)break;
}
if(count.size()>=1)
{
for(k=count.begin(),p=l.begin(); k!=count.end(); p++, k++)
if(*k==i)break;
}
elsek=count.end();
if(k==count.end())
{
count.push_back(i);
q queue1;
queue1.push(c);
l.push_back(queue1);
}
else(*p).push(c);
}
elseif(strcmp(s,"DEQUEUE")==0)
{
printf("%ldn",l.front().front());
l.front().pop();
if(l.front().size()==0)
{
l.pop_front();
count.pop_front();
}
}
memset(s,0,sizeof(s));
}
printf("n");
}
cx++;
}
return0;
}