The kth great number

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65768/65768K (Java/Other)
Total Submission(s) : 3   Accepted Submission(s) : 2

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.

Input

There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an " I" followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a "Q", then you need to output the kth great number.

Output

The output consists of one integer representing the largest number of islands that all lie on one line.

Sample Input

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

Sample Output

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).

Source

The 36th ACM/ICPC Asia Regional Dalian Site —— Online Contest 



思路：
题意就是，有插入操作和询问操作，问每次询问时的第k大数是多少。一开始的想法是暴力，每次在询问的时候都排个序，果断TLE...这让我想起来之前做过的一道Sliding Window，那个题也是这样要求一个第k最值。然后就想到了用优先队列的方法去求，按照大数优先的原则，使大数集中在队列尾，最小数集中在队列头。然后就用一个长度为k的队列，那样的话队首就是k个数里面最小的，也就是第k大的那个数。在队列未满之前，可以一直push，并且能够产生顺序；在队列满了之后，就要对每次输入的数进行判断，如果输入数小于队头则不进队，输入数大于队头则进队，弹出队头。这样就保证了第k大数永远在队首，方便使用top操作。


代码： 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;

struct Node
{
    int x;
    friend bool operator < (Node a,Node b)
    {
        return a.x > b.x;
    }
};

int main()
{
	//freopen("in.txt","r",stdin);
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		priority_queue <Node> q;
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			char b;
			cin>>b;
			if(b=='I')
			{
				if(cnt<k)
				{
					Node num;
					scanf("%d",&(num.x));
					cnt++;
					q.push(num);
				}
				else if(cnt>=k)
				{
					Node num;
					scanf("%d",&(num.x));
					if(num.x>q.top().x)
					{
						q.pop();
						q.push(num);
					}
				}
			}
			else if(b=='Q')
			{
				printf("%d\n",q.top().x);
			}
		}		
	}	
	return 0;
}