hdu 4006 The kth great number 线段树/优先队列/set

题目意思：

    有n种操作，I代表插入数据，q代表输出第k大的数。

区间的大数据的操作，基本是用树操作。

这到题目可以用三种方法来做。

（1） 线段树

考虑到题目可能有负数，给每个值加500000直接贴代码。

s[k].n代表在这个区间内的数的个数。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,k;
const int N=1500005;
struct node
{
    int l, r;
    int n;
}s[N*4+1100];

void bulid(int l,int r,int k)
{
    if(l==r){
        s[k].l=l;
        s[k].r=r;
        s[k].n=0;
        return ;
    }
    s[k].l=l;
    s[k].r=r;
    s[k].n=0;
    int mid=(l+r)>>1;
    bulid(l,mid,k<<1);
    bulid(mid+1,r,k<<1|1);
    s[k].n=s[2*k].n+s[2*k+1].n;
}

void Insert(int d,int k)
{
    if(s[k].l==s[k].r&&s[k].l==d)
    {
        s[k].n++;
        return;
    }
    int mid=(s[k].l+s[k].r)/2;
    if(d<=mid) Insert(d,2*k);
    else  Insert(d,2*k+1);
    s[k].n=s[2*k].n+s[2*k+1].n;
}

int query(int k,int a)
{
    if(s[k].l==s[k].r){
        return s[k].l;
    }
    int ans;
    if(a<=s[k<<1].n) ans=query(k<<1,a);
    else if(a>s[k<<1].n) ans=query(k<<1|1,a-s[k<<1].n);
    s[k].n=s[2*k].n+s[2*k+1].n;
    return ans;
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF){
        bulid(1,N,1);
        getchar();
        int total=0;
        for(int i=1;i<=n;i++){
            char c;
            scanf("%c",&c);
            getchar();
            if(c==‘I‘){
                 int tt;
                 scanf("%d",&tt);
                 getchar();
                Insert(tt+500000,1);
                total++;
            }
            else if(c==‘Q‘){
                printf("%d\n",query(1,total-k+1)-500000);
            }
        }
    }
}

用优先队列。

优先队列内部维护一个堆。

优先队列中只要维护k个数就好。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Node
{
    int a;
    friend bool operator < (const struct Node n1,const struct Node n2){
        return n1.a>n2.a;
    }
};
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF){
        getchar();
        priority_queue<Node>q;
        for(int i=1;i<=n;i++){
            char c;
            scanf("%c",&c);
            getchar();
            if(c==‘I‘){
                Node tt;
                scanf("%d",&tt.a);
                getchar();
                q.push(tt);
                while(q.size()>k){
                    q.pop();
                }
            }
            else {
                printf("%d\n",q.top().a);
            }
        }
    }
}

set内部维护一颗红黑树。

参见：http://blog.csdn.net/cnh294141800/article/details/21657969

#include<stdio.h>
#include<iostream>
#include<set>
using namespace std;
int main()
{
	int n,i,j,m,k;
	while(scanf("%d %d",&n,&k)!=EOF)
	{
		 multiset<int>s;
		 multiset<int>::iterator it;
		 for(i=0;i<n;i++)
		 {
			 char a[2];
			 scanf("%s",a);
			 if(a[0]==‘I‘)
			 {
				 scanf("%d",&m);
				 s.insert(m);
				 if(s.size()>k)
					 s.erase(s.begin());
			 }
			 else
			 {
				 printf("%d\n",*s.begin());
			 }
		 }
	}
	return 0;
}

hdu 4006 The kth great number 线段树/优先队列/set,布布扣,bubuko.com

hdu 4006 The kth great number 线段树/优先队列/set

原文：http://blog.csdn.net/cnh294141800/article/details/22601963