http://acm.hdu.edu.cn/showproblem.php?pid=4251
n個數(shù),求給定區(qū)間中間大小的元素的值
1 #include<cstdio> 2 #include< string > 3 #include<vector> 4 #include<algorithm> 5 #define N 100009 6 using namespace std; 7 int n; 8 int arr[N]; // 原數(shù)據(jù) 9 int od[N]; // 排序后 10 int lfnum[ 20 ][N]; // 元素所在區(qū)間的當前位置進入左孩子的元素的個數(shù) 11 int val[ 20 ][N]; // 記錄第k層當前位置的元素的值 12 bool cmp( const int &x, const int &y){ return arr[x]< arr[y];} 13 void build( int l, int r, int d) 14 { 15 if (l==r) return ; 16 int mid=(l+r)>> 1 ,p= 0 ; 17 for ( int i=l;i<=r;i++ ) 18 { 19 if (val[d][i]<= mid) 20 { 21 val[d+ 1 ][l+p]= val[d][i]; 22 lfnum[d][i]=++ p; 23 } 24 else 25 { 26 lfnum[d][i]= p; 27 val[d+ 1 ][mid+i+ 1 -l-p]= val[d][i]; 28 } 29 } 30 build(l,mid,d+ 1 ); 31 build(mid+ 1 ,r,d+ 1 ); 32 } 33 // 求區(qū)間[s,e]第k大的元素 34 int query( int s, int e, int k, int l= 1 , int r=n, int d= 0 ) 35 { 36 if (l==r) return l; 37 int mid=(l+r)>> 1 ,ss,ee; 38 ss=(s==l? 0 :lfnum[d][s- 1 ]); 39 ee= lfnum[d][e]; 40 if (ee-ss>=k) return query(l+ss,l+ee- 1 ,k,l,mid,d+ 1 ); 41 return query(mid+ 1 +(s-l-ss),mid+ 1 +(e-l-ee),k-(ee-ss),mid+ 1 ,r,d+ 1 ); 42 } 43 int main() 44 { 45 int cas= 0 ,m,l,r; 46 while (scanf( " %d " ,&n)!= EOF) 47 { 48 printf( " Case %d:\n " ,++ cas); 49 for ( int i= 1 ;i<=n;i++) scanf( " %d " ,arr+i),od[i]= i; 50 sort(od+ 1 ,od+n+ 1 ,cmp); 51 for ( int i= 1 ;i<=n;i++) val[ 0 ][od[i]]= i; 52 build( 1 ,n, 0 ); 53 scanf( " %d " ,& m); 54 while (m-- ) 55 { 56 int num,k; 57 scanf( " %d%d " ,&l,& r); 58 k=(r-l)/ 2 + 1 ; // 中間大小 59 num= query(l,r,k); 60 int ans= arr[od[num]]; 61 printf( " %d\n " ,ans); 62 } 63 } 64 }
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
