UVA 540 Team Queue

思路：使用优先队列，按队伍出现的时刻和自身出现的时刻定义优先级，同时记录此时刻队列里是否有自己队伍的人，一开始没注意，wa了两发。

#include<map>

#include<queue>

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN = 1010;

map<int, int>mp;

int teamPos[MAXN],existElem[MAXN], T, n;

struct Elem{

    int idx, pos, self;

    Elem(int idx, int pos, int self){

        this->pos = pos;

        this->idx = idx;

        this->self = self;

    }

    bool operator < (const Elem &A) const {

        if(idx == A.idx) return pos > A.pos;

        return idx > A.idx;

    }

};

int main(){

    string str;

    int elemNum, CASE(0);

    freopen("in.cpp", "r", stdin);

    while(~scanf("%d", &T) && T){

        mp.clear();

        priority_queue<Elem>Q;

        while(!Q.empty()) Q.pop();

        for(int i = 1;i <= T;i ++){

            scanf("%d", &n);

            for(int j = 0;j < n;j ++){

                scanf("%d", &elemNum);

                mp.insert(pair<int, int>(elemNum, i));

            }

        }

        int num(0), cnt(0);

        memset(teamPos, 0, sizeof teamPos);

        memset(existElem, 0, sizeof existElem);

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

        while(cin >> str && str[0] != 'S'){

            if(str[0] == 'D'){

                int tmp = Q.top().self;

                printf("%d\n",tmp);

                map<int, int>::iterator it = mp.find(tmp);

                existElem[it->second] --;

                Q.pop();

                continue;

            }

            scanf("%d", &n);

            map<int, int>::iterator it = mp.find(n);

            int idx = it->second;

            if(teamPos[idx] && existElem[idx]) Q.push(Elem(teamPos[idx], cnt++, n));

            else{

                Q.push(Elem(++num, cnt++, n));

                teamPos[idx] = num;

            }

            existElem[idx]++;

        }

        puts("");

    }

    return 0;

}