Posted on 2010-08-18 22:52
Uriel 阅读(595)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
数据结构
这题貌似最优解法是SBT,这个只看过,完全没有敲过,想到STL set,于是水过去了。。。
对于STL,现在基本也只会priority queue, set, heap, map还基本没怎么写过,只能应付应付比赛的时候最基本的用法。。。
这题用set,C++比G++快一倍,282Ms,有点慢,不过代码量很少~~
//Problem: 3481 User: Uriel
//Memory: 840K Time: 282MS
//Language: C++ Result: Accepted
//Version: STL => set
//2010.08.18
#include<set>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
int id,p;
}q;
bool operator<(const node &a,const node &b){
return a.p>b.p;
}
int main(){
int x;
set<node> st;
while(scanf("%d",&x),x){
if(x==1){
scanf("%d %d",&q.id,&q.p);
st.insert(q);
}
else if(x==2){
if(st.empty()){
puts("0");
continue;
}
printf("%d\n",st.begin()->id);
st.erase(st.begin());
}
else if(x==3){
if(st.empty()){
puts("0");
continue;
}
set<node>::iterator it;
it=st.end();
it--;
printf("%d\n",it->id);
st.erase(st.find(*it));
}
}
return 0;
}