CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
#include <iostream>
#include
<cstdio>
#include
<cstring>
using namespace std;

const int MAX_VAL = 300000//输入的数字范围 

int c[MAX_VAL+5];
int delta;

inline 
int lowbit(int x){return x&(-x);}

 
void add(int p,int x)
{
    
while(p<=MAX_VAL)
    {
        c[p]
+=x;
        p
+=lowbit(p);
    }
}

int find_kth(int K)
{
    
int ans = 0,cnt = 0;
    
for(int i=19;i>=0;i--)//这里的19适当的取值,与MAX_VAL有关,一般取lg(MAX_VAL) 
    {
        ans
+=(1<<i);
        
if(ans>= MAX_VAL||cnt+c[ans]>= K)ans-=(1<<i);
        
else cnt+=c[ans];
    }
    
return ans+1;
}
int main()
{
    
int n;
    
int x, k, i;
    
while (cin >> n)
    {
        memset(c, 
0sizeof(c));
        
for (i = 0; i < n; i++)
        {
            scanf(
"%d"&x);
            add(x, 
1);
        }
        cin 
>> n;
        
for (i = 0; i < n; i++)
        {
            cin 
>> k;
            cout 
<< find_kth(k) << endl;
        }
    } 
    
return 0;
}
posted on 2011-05-13 16:47 CodeStream 阅读(894) 评论(1)  编辑 收藏 引用

评论

# re: 树状数组 求第k大 2016-08-18 18:25 zyzhang
请教博主,关于用树状数组求第k大的数有什么限定条件吗,因为我把add(x,1)改为add(x,2)运行出来的结果与所期望的到的不一致。  回复  更多评论
  


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