uva 540 Team Queue

思路: list+map模擬
分析:
1 題目的意思是有n個隊伍，每個隊伍的人數為m。
2 現在有三種操作，ENQUEUE x是插入x，如果隊列裡面已經有x這一隊的成員那麼直接插入到這一隊的最後一個，否則插入到隊列的最後一個；DEQUEUE 是直接拿到隊列的第一個元素輸出，並刪除隊列的第一個元素；STOP是停止
3 直接利用map和list來模擬，由於題目要求要插入的具體的位置所以用list來模擬

代碼:

#include<map>
#include<list>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;

map<int , int>mp;
list<int>ls;
list<int>:: iterator it[MAXN];
int cnt[MAXN];

void insert(int x){
    if(ls.size() == 0){
        ls.push_back(x);
        it[mp[x]] = ls.begin();
        return; 
    }   
    int tmp = mp[x];
    if(it[tmp] == ls.end()){
        ls.push_back(x); 
        it[tmp] = ls.end();
        it[tmp]--;
    }
    else{
        list<int>:: iterator tmpIt = it[tmp];
        ls.insert(++tmpIt , x);
        it[tmp]++;
    }
}

int main(){
    int n , m , x;
    int Case = 1;
    char str[20];
    while(scanf("%d" , &n) && n){
         mp.clear();
         ls.clear();
         for(int i = 1 ; i < MAXN ; i++)
             it[i] = ls.end();
         memset(cnt , 0 , sizeof(cnt));
         printf("Scenario #%d\n" , Case++);
         for(int i = 1 ; i <= n ; i++){
             scanf("%d" , &m);
             while(m--){
                  scanf("%d" , &x); 
                  mp[x] = i;
             } 
         }
         while(scanf("%s" , str) && str[0] != 'S'){
             if(str[0] == 'E'){
                 scanf("%d" , &x);
                 insert(x);
                 cnt[mp[x]]++;
             }
             else{
                 int front = ls.front();
                 ls.pop_front();
                 int tmp = mp[front];
                 printf("%d\n" , front);
                 cnt[tmp]--;
                 if(cnt[tmp] == 0)
                     it[tmp] = ls.end();
             }
         }
         puts("");
    }
    return 0;
}