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;
}
上一篇:chrome浏览器设置小于12号的字体不起作用?


下一篇:SQL注入原理深度解析