首页 > 代码库 > poj 1442
poj 1442
两种操作， add：是向序列中加入一个数 ， get是问第k小数是谁 ， 可以用优先队列 ， 也可以用treap ， 还可以用线段树 。
线段树的做法为 ， 先离散化 ， 然后每次都往线段树中加入数 ， 线段树相应的的点+1 ， 然后可以二分找 。 思想很明显， 代码实现注意细节就行 ， 不过我没去写了。这里只给出2种解法。
1：优先队列：两个优先队列， 一个最小优先 ， 一个最大优先， 最大优先保存前i-1小的数 ， 最小优先里面的数都比最大优先的大 ，那么每次询问第i小的数时 ， 最小优先队列的第一个就是答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 7 const int N = 33333 ; 8 9 using namespace std ;10 11 priority_queue<int , vector<int> , greater<int> >Min_Q ;12 priority_queue<int , vector<int> , less<int> >Max_Q ;13 14 int val[N] , n , m ;15 16 int main()17 {18 while( scanf("%d%d" , &n , &m)==2 )19 {20 for( int i=1;i<=n;i++ ) scanf("%d" , &val[i]);21 22 while( !Min_Q.empty() ) Min_Q.pop() ;23 while( !Max_Q.empty() ) Max_Q.pop() ;24 25 int p = 0 , rank = 1 , v ;26 27 for( int i=1;i<=m;i++ ){28 29 30 scanf("%d" , &v) ;31 32 while( v>p ){33 int num = val[++p] ;34 35 if( Max_Q.size()<rank-1 ) Max_Q.push( num ) ;36 37 else if( Max_Q.empty() || num>=Max_Q.top() ){38 Min_Q.push( num ) ; 39 } 40 else{41 Min_Q.push( Max_Q.top() );42 Max_Q.pop() ;43 Max_Q.push( num ) ; 44 } 45 } 46 47 printf("%d\n" , Min_Q.top()) ;48 Max_Q.push( Min_Q.top() ) ;49 Min_Q.pop() ;50 rank++ ;51 } 52 }53 }
2：treap， 模板题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 7 const int N = 33333 ; 8 9 using namespace std ;10 11 int val[N] , n , m , ans ;12 13 struct node{14 node * ch[2] ;15 int s , v , r ;16 node(){17 ch[0] = ch[1] = NULL ;18 s = 1 ; 19 } 20 int cmp( int x )const{21 if( x==v ) return -1 ;22 return x<v?0:1 ; 23 }24 void maintain(){25 s = 1 ;26 if( ch[0]!=NULL ) s += ch[0]->s ;27 if( ch[1]!=NULL ) s += ch[1]->s ; 28 }29 };30 31 void rotate( node * &o , int d ){32 node * k = o->ch[d^1] ;33 o->ch[d^1] = k->ch[d] ;34 k->ch[d] = o ;35 o->maintain() ; k->maintain() ;36 o = k ; 37 }38 39 bool find_x( node * o , int x ){40 while( o!=NULL ){41 int d = o->cmp(x) ;42 if( d==-1 ) return true ;43 else o = o->ch[d] ; 44 }45 return false ; 46 }47 48 void insert( node * &o , int x ){49 if( o==NULL ){50 o = new node() ;51 o->v = x ; o->r = rand() ;52 return ; 53 } 54 55 int d = o->cmp(x) ;56 57 if( d==-1 ) d = 1 ;58 insert( o->ch[d] , x ) ;59 if( o->ch[d]->r > o->r ) rotate( o , d^1 ) ;60 o->maintain() ;61 }62 63 bool findkth( node * o , int k ){64 while( o!=NULL ){65 if( o->s<k ) return false ;66 int l = o->ch[0]!=NULL ? o->ch[0]->s : 0 ;67 68 if( l+1==k ){69 ans = o->v ;70 return true ; 71 } 72 73 int d = l<k ;74 o = o->ch[d] ;75 k -= d*(l+1) ;76 } 77 return false ;78 }79 80 int main()81 {82 while( scanf("%d%d" , &n , &m)==2 ){83 for( int i=1;i<=n;i++ ) scanf("%d" , &val[i]) ;84 85 int p = 0 , rank = 1 , v;86 87 node * root = NULL ;88 for( int i=1;i<=m;i++ ){89 scanf("%d" , &v);90 91 while( v>p ) insert( root , val[++p] ) ;//, cout<<p<<" "<<val[p]<<endl;92 93 if( findkth( root , rank++ )==true )94 printf("%d\n" , ans); 95 } 96 } 97 }
poj 1442
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。