Uva 540 Team Queue

点击打开链接

题目意思：有很多个队，然后每个队都有自己的成员，如果遇到ENQUEUE 就把该元素插入到自己队伍里面，如果没有自己的队伍那么就插入到最后面，遇到DEQUEUE就输出第一个元素，遇到STOP就停止

解题思路：首先题目的数据很大，如果我们暴力肯定会TLE  ，我们用list链表，那么我们可以开一个mark[1000000]用来存储是否有这个元素，还有同一队的元素赋值为相同，那么我们再开一个迭代器数组it[1010],用来存储每一组的最后一个元素的地址个，还有初始化迭代器数组为末尾。所以我们就可以在查找时候根据it[mark[ele]]是否为end(),,如果是说明队伍中还没有该队成员，此时直接插入末尾，否则++it[mark[ele],这里把指向该组最后元素的指针向后一个（这个元素不是该组的），然后插入ele这个元素（因为是要插入到该组的后面），但是我们还要把指针减一（即指回新插入的元素）

注意事项：我们遇到DEQUEUE时候要remove第一个元素，但是我们要注意如果这时候刚好把某一组的所有元素都删除了，我们要从新把标记改组的迭代器值改为end();（即判断是否lis.begin() == it[mark[lis.front()]]）;就是是否有第一个元素是不是所在组的最后一个）

代码：

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

int t , n , ele;
int tnum[1010] , mark[1000010];//用mark数组来标记该元素属于某一组
string str;
list<int>lis;
list<int>::iterator it[1010];//迭代器数组用来存储一组的最后一个元素的指针
//初始化函数
void init(){
    int i;
    memset(tnum , 0 , sizeof(tnum));
    memset(mark , 0 , sizeof(mark));
    for(i = 0 ; i < 1010 ; i++)
        it[i] = lis.end();//要把迭代器初始化为lis.end()
}
//处理函数
void solve(int ele){
    int i ,j;
    if(it[mark[ele]] == lis.end()){//如果该元数所在组的最后一个元素为lis.end()
        lis.push_back(ele);//直接插入到后面
        it[mark[ele]] = --it[mark[ele]];//这时候该组最后一个元素的地址即lis.end()减1即可
    }
    else{
        lis.insert(++it[mark[ele]] , ele);//先把指向最后一个元素的地址加一，指向别组的元素，注意指针是不会随便改的
        it[mark[ele]]--;//还要把指针减1，指回刚插入的元素
    }
}
//主函数
int main(){
    int i , j, k ,element ,  Mark;
    k = 1;
    while(scanf("%d" , &t) && t){
        init();
        Mark = 0;
        for(i = 0 ; i < t ; i++){
            cin>>tnum[0];
            for(j = 1 ; j <= tnum[0] ; j++){
                scanf("%d" ,&element);
                mark[element] = i + 1;//同一组的标记为相同数字
            }
        }
        printf("Scenario #%d\n" ,k);
        while(cin>>str){
            if(str == "STOP")
                break;
            if(str == "ENQUEUE"){
                scanf("%d" , &ele);
                solve(ele);
            }
            if(str == "DEQUEUE"){
                cout<<lis.front()<<endl;
                //移掉一个元素判断一下是否为该组的末尾元素，如果是就要从新赋给新的地址
                if(lis.begin() == it[mark[lis.front()]]){
                    it[mark[lis.front()]] = lis.end();//重新更新为lis.end()说明队伍里面已经没有该组的成员了
                }
                lis.pop_front();//删除第一个
            }
        }
        k++;
        cout<<endl;
        lis.clear();//清除链表
    }
    return 0;
}