思路相当简单，主要在于实现！
team[i]表示编号为i的人所在的队；
last[i]表示第i个队的、在队列中最靠后的人的位置。
这样一来，就需要支持快速插入和删除的数据结构：链表。
正在我苦恼不知道如何用list<int>::iterator、insert和pop_front处理的时候，郁闷难道还要自己实现链表的时候，我翻翻书，发现insert是有返回值的函数，这样就OK了。
依然不晓得迭代器如何像指针赋值NULL一样表示无效，另外开了一个list，无效则指向这个list的end()。
以下是我的代码：
#include<list>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(1007);
const char kEnqueue[]="ENQUEUE";
const char kDequeue[]="DEQUEUE";
const char kStop[]="STOP";
int team[1000000];
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T(0),n;
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
for(int j=1;j<=t;j++)
{
int t2;
scanf("%d",&t2);
team[t2]=i;
}
}
T++;
printf("Scenario #%d\n",T);
list<int> l,lt;
list<int>::iterator last[kMaxn];
for(int i=1;i<=n;i++)
last[i]=lt.end();
char cmd[17];
while(scanf("%s",cmd) && strcmp(cmd,kStop))
{
if(strcmp(cmd,kEnqueue)==0)
{
int t;
scanf("%d",&t);
if(last[team[t]]==lt.end())
last[team[t]]=l.insert(l.end(),t);
else
{
last[team[t]]++;
last[team[t]]=l.insert(last[team[t]],t);
}
}
else
{
int t(l.front());
printf("%d\n",t);
list<int>::iterator ti(l.begin());
if(ti==last[team[t]])
last[team[t]]=lt.end();
l.pop_front();
}
}
printf("\n");
}
return 0;
}
posted on 2011-04-14 16:41
lee1r 阅读(1209)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构