POJ2104-K-th Number-求区间第K大数(暴力or归并树or划分树) - c++编程基础

TOP

POJ2104-K-th Number-求区间第K大数(暴力or归并树or划分树)

2015-11-21 00:55:33 来源: 作者: 【大中小】浏览:1次

题目意思很简单，就是给你一个序列，查询某区间第K大的数；

方法1：时间复杂度O(N*M)；不支持更新操作，代码简单；

利用结构体排序，保留原数据的顺序。

#include 
  
   
#include 
   
     #include 
    
      #define N 100000 using namespace std; /* 这个思路很好；时间复杂度O(n*m)； 不过还好这个题目给的数据量不大，而且时间限制给了2s，所以可以很轻松的过； */ struct NODE { int x,id; }node[N]; bool cmp(NODE a,NODE b) { return a.x
     
      =a&&node[j].id<=b) k--; if(!k) { printf(%d ,node[j].x); break; } } } } return 0; }

方法2：归并树，时间复杂度O(nlogn+mlong^3(n))；利用归并排序，用线段树位数数组顺序；

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #define LL long long #define inf 1<<30 #define s(a) scanf(%d,&a) #define Clear(a,b) memset(a,b,sizeof(a)) using namespace std; /* O(nlogn+mlog^3(n)) */ const int N=200005; int n,m,a,b; int seg[25][N]; int num[N]; void Merge_Sort(int l,int r,int deep) // 每一层保留该层已经排好的数据； { int mid=(l+r)>>1; int i=l,j=mid+1,k=l; while(i<=mid&&j<=r){ if(seg[deep+1][i]<=seg[deep+1][j]){ seg[deep][k++]=seg[deep+1][i++]; }else{ seg[deep][k++]=seg[deep+1][j++]; } } while(j<=r){ seg[deep][k++]=seg[deep+1][j++]; } while(i<=mid){ seg[deep][k++]=seg[deep+1][i++]; } } void Build(int l,int r,int rt,int deep) // 建树；deep根节点的深度； { if(l==r){ seg[deep][l]=num[l]; // 单叶子节点按输入的顺序存数据； return; } int mid=(l+r)>>1; Build(l,mid,rt<<1,deep+1); Build(mid+1,r,rt<<1|1,deep+1); Merge_Sort(l,r,deep); // 归并排序； } int Query(int v,int deep,int L,int R,int l,int r,int rt) // 查询[L,R]区间比v小的数有多少个； { if(r
             
              =r){ return lower_bound(&seg[deep][l],&seg[deep][r]+1,v)-&seg[deep][l]; // 返回第一个大于等于v的下标； } int mid=(l+r)>>1; return Query(v,deep+1,L,R,l,mid,rt<<1)+Query(v,deep+1,L,R,mid+1,r,rt<<1|1); } int Solve(int l,int r,int k){ // 二分查找[L,R]，降低时间复杂度； int L=1,R=n,mid; while(L
              
               >1; // 这里要特别注意；mid=(L+R+1)>>1;不是mid=(L+R)>>1; int cnt=Query(seg[1][mid],1,l,r,1,n,1); // 返回比v小的个数； if(cnt<=k){ // 如果小于等于我们要查找的k，说明seg[1][mid]这个数太小了，网右边查找； L=mid; }else{ R=mid-1; } } return seg[1][L]; } int main() { while(~scanf(%d%d,&n,&m)){ for(int i=1;i<=n;i++) s(num[i]); Build(1,n,1,1); while(m--){ int l,r,k; s(l);s(r);s(k); printf(%d ,Solve(l,r,k-1)); // 这里也值得注意一下，输入的是k-1,不是k； } } return 0; }

方法3：划分树;好吧，这个思路我还没有整理好，给这个牛逼算法留一块空地；^_^....
?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu3549Flow Problem 最大流模板..	下一篇：UVA - 1456 Cellular Network

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: