uva 540 Team Queue

点击打开链接uva 540

思路: 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;
}