题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1387
我的思路:用一个优先队列,队伍入队顺序作为优先级,同队伍的元素入队顺序作为结构体id,用vis数组标记队伍,优先队列内部自动根据pri和id排序
wa代码:
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=1e6+3;
int team[maxn];
int ans[1003];//用来比较队伍优先级
int vis[1003];//标记已经入队的队伍
struct node{
int pri;
int id;
int value;
friend bool operator<(node n1,node n2){
if(n1.pri==n2.pri)return n1.id>n2.id;
return n1.pri>n2.pri;
}
};
int t;//队伍数量
void Init()
{
memset(team,0,sizeof(team));
int i=1;
for(;i<=t;++i){
int n,cnt;
scanf("%d",&n);
node nd;
for(int j=1;j<=n;++j){
scanf("%d",&cnt);
team[cnt]=i;
}
}
}
int main()
{
int kase=0;//案例编号
while(~scanf("%d",&t)&&t!=0){
node nd;
priority_queue<node> q;
Init();
memset(ans,0,sizeof(ans));
memset(vis,0,sizeof(vis));
printf("Scenario #%d\n",++kase);
char s[10];
int num=0,cnt=0;
while(~scanf("%s",s)){
getchar();
if(s[0]=='E'){
cnt++;
int cd;
scanf("%d",&cd);
nd.value=cd;
if(!team[cd])team[cd]=++t;//如果是没有出现过的元素赋给新的队伍插入前面队伍的队尾
if(!vis[team[cd]]){
++num;
ans[team[cd]]=num;
}
nd.id=cnt;
nd.pri=ans[team[cd]];
q.push(nd);
vis[team[cd]]=1;
}else if(s[0]=='D'){
nd=q.top();
team[nd.value]=0;//元素出队后要把它的痕迹清除
vis[team[nd.value]]=0;
q.pop();
printf("%d\n",nd.value);
}else if(s[0]=='S'){
printf("\n");
break;
}
}
}
return 0;
}
一直都是wa,真的是整自闭了,我看我们学长的题解用的是两个队列维护,但是我想搞清楚我这种思路到底为什么会wa,一个优先队列为什么不行呢?还是说我哪里写的有问题?题解也看了不少,但是一直没能解决,拜托各位大牛帮忙看看可以吗?谢谢了