Posted on 2010-08-18 22:52
Uriel 閱讀(610)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
數(shù)據(jù)結(jié)構(gòu)
這題貌似最優(yōu)解法是SBT，這個(gè)只看過(guò)，完全沒(méi)有敲過(guò)，想到STL set，于是水過(guò)去了。。。
對(duì)于STL，現(xiàn)在基本也只會(huì)priority queue, set, heap, map還基本沒(méi)怎么寫過(guò)，只能應(yīng)付應(yīng)付比賽的時(shí)候最基本的用法。。。
這題用set，C++比G++快一倍，282Ms，有點(diǎn)慢，不過(guò)代碼量很少~~
//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;
}