Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3481 Double Queue---SBT/STL

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;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理