The kth great number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 5929    Accepted Submission(s): 2404

8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

1
2
3

Hint
Xiao  Ming  won‘t  ask  Xiao  Bao  the  kth  great  number  when  the  number  of  the  written number is smaller than k. (1=<k<=n<=1000000).

解法一：用优先队列

#include"stdio.h"
#include"queue"
using namespace std;
struct node 
{
	int x;
	friend bool operator<(node a,node b)
	{
		return a.x>b.x;
	}
};
int main()
{
	int n,k,i;
	char ch;
	while(scanf("%d%d",&n,&k)!=-1)
	{
		priority_queue<node>q; //注意：因为是多实例，故把队列定义循环里面可以清空队列
    	node p;
		while(n--)
		{
			getchar();
			scanf("%c",&ch);
			if(ch==‘I‘)
			{
				scanf("%d",&i);
				p.x=i;
				q.push(p);
				if(q.size()>k)
					q.pop();
			}
			else
			{
				p=q.top();
				printf("%d\n",p.x);
			}
		}
	}
	return 0;
}

解法二：可以把数组控制大小为k,前k个元素挨个输入数组；

满足k个元素后快排，从大到小，第K个元素就是第K小的；

然后，每输入一个元素和第K小元素比较大小，维护数组；

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1000010
static int a[N];
int n,k,m;
int cmp(const void *a,const void*b)
{
    return *(int *)a>*(int *)b?-1:1;   
}
void inti(int t)
{
    int i,j;
    if(m<k)
        a[m++]=t;         
    else if(m==k)          
    {
        a[m++]=t;
        qsort(a,m,sizeof(a[0]),cmp);
    }
    else
    {
        if(t>a[k])
        {
            for(i=k;i>=0;i--)
                if(a[i]>t)
                    break;
            for(j=k;j>i+1;j--)
                a[j]=a[j-1];
            a[i+1]=t;
        }
    }
}
int main()
{
    int t;
    char ch;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        k--;
        getchar();
        m=0;
        while(n--)
        {
            scanf("%c",&ch);
            if(ch==‘I‘)
            {
                scanf("%d",&t);
                inti(t);
            }
            else
                printf("%d\n",a[k]);
            getchar();
        }
    }
    return 0;
}

hdu 4006 The kth great number,布布扣,bubuko.com

hdu 4006 The kth great number

原文：http://blog.csdn.net/u011721440/article/details/20639251