Posted on 2010-08-18 22:52
Uriel 閱讀(619)
評論(0) 編輯 收藏 引用 所屬分類:
POJ 、
數(shù)據(jù)結構
這題貌似最優(yōu)解法是SBT，這個只看過，完全沒有敲過，想到STL set，于是水過去了。。。
對于STL，現(xiàn)在基本也只會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;
}