思路相當簡單，主要在于實現！
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 閱讀(1231)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構