Hoj 1456 Team Queue

團隊隊列。

方法一：直接用鏈表模擬，用STL list直接模擬。

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <vector>  
#include <queue>  
#include <list>  
#include <algorithm>  
using namespace std; 
 
int team[1000005]; 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int t; 
    int cas = 0; 
    char cmd[20]; 
    list<int> q; 
    list<int> final; 
    list<int>::iterator last[1005]; 
    while(scanf(" %d",&t)!=EOF && t!=0) 
    { 
        q.clear(); 
        final.clear(); 
        cas++; 
        int num,t1; 
 
        for(int i=1; i<=t; i++) 
        { 
            scanf(" %d",&num); 
            for(int j=0; j<num; j++) 
            { 
                scanf(" %d",&t1); 
                team[t1] = i; 
            } 
        } 
 
        for(int i=1; i<=t; i++) last[i] = q.end(); 
 
        printf("Scenario #%d\n",cas); 
 
        while(scanf(" %s",cmd)!=EOF && strcmp(cmd,"STOP")!=0) 
        { 
            if(strcmp(cmd,"ENQUEUE") == 0) 
            { 
                int w; 
                scanf("%d",&w); 
                if(last[team[w]]==q.end()) 
                    last[team[w]]=final.insert(final.end(),w); 
                else 
                { 
                    last[team[w]]++; 
                    last[team[w]]=final.insert(last[team[w]],w); 
                } 
            } 
            else if(strcmp(cmd,"DEQUEUE") == 0) 
            { 
                int temp = final.front(); 
                printf("%d\n",temp); 
                list<int>::iterator ti = final.begin(); 
                if(ti == last[team[temp]]) 
                    last[team[temp]] = q.end(); 
                final.pop_front(); 
            } 
        } 
        printf("\n"); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;

int team[1000005];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int t;
    int cas = 0;
    char cmd[20];
    list<int> q;
    list<int> final;
    list<int>::iterator last[1005];
    while(scanf(" %d",&t)!=EOF && t!=0)
    {
        q.clear();
        final.clear();
        cas++;
        int num,t1;

        for(int i=1; i<=t; i++)
        {
            scanf(" %d",&num);
            for(int j=0; j<num; j++)
            {
                scanf(" %d",&t1);
                team[t1] = i;
            }
        }

        for(int i=1; i<=t; i++) last[i] = q.end();

        printf("Scenario #%d\n",cas);

        while(scanf(" %s",cmd)!=EOF && strcmp(cmd,"STOP")!=0)
        {
            if(strcmp(cmd,"ENQUEUE") == 0)
            {
                int w;
                scanf("%d",&w);
                if(last[team[w]]==q.end())
                    last[team[w]]=final.insert(final.end(),w);
                else
                {
                    last[team[w]]++;
                    last[team[w]]=final.insert(last[team[w]],w);
                }
            }
            else if(strcmp(cmd,"DEQUEUE") == 0)
            {
                int temp = final.front();
                printf("%d\n",temp);
                list<int>::iterator ti = final.begin();
                if(ti == last[team[temp]])
                    last[team[temp]] = q.end();
                final.pop_front();
            }
        }
        printf("\n");
    }
    return 0;
}
方法二：開1000個小隊列，一個大隊列模擬。

[cpp]
#include <cstdio>  
#include <cstring>  
#include <queue>  
 
using namespace std; 
 
int v[1000100]; 
bool flag[1010]; 
queue <int> q,cyr[1010]; 
 
int main() 
{ 
  int T,n,x,i,j,temp,u; 
  char e[50]; 
  scanf("%d",&T); 
  temp=0; 
  while (T!=0) 
  { 
    temp++; 
    memset(v,0,sizeof(v)); 
    memset(flag,true,sizeof(flag)); 
    printf("Scenario #%d\n",temp); 
    while (!q.empty()) 
      q.pop(); 
    for (i=1;i<=T;i++) 
    { 
      scanf("%d",&n); 
      for (j=1;j<=n;j++) 
      { 
        scanf("%d",&x); 
        v[x]=i; 
      } 
    } 
    scanf("%s",e); 
    while (e[0]!='S') 
    { 
      if (e[0]=='E')  
      { 
        scanf("%d",&x); 
        u=v[x]; 
        cyr[u].push(x); 
        if (flag[u]) 
        { 
          flag[u]=false; 
          q.push(u); 
        } 
      } 
      if (e[0]=='D') 
      { 
        u=q.front(); 
        while (cyr[u].empty())  
        { 
          flag[u]=true; 
          q.pop();  
          u=q.front(); 
        } 
        x=cyr[u].front(); 
        cyr[u].pop(); 
        printf("%d\n",x); 
      } 
      scanf("%s",e); 
    } 
    for (i=1;i<=n;i++) 
      while (!cyr[i].empty()) cyr[i].pop(); 
    printf("\n"); 
    scanf("%d",&T); 
  } 
  return 0; 
}