The kth great number multiset应用（找第k大值）

The kth great number

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



开一个multiset（允许存在相同值的集合且加入后自动排序），维护k个元素，多出在头部删除，最后取第一个元素即可,适用于找第几大第几小的题。

#include<stdio.h>
#include<set>
using namespace std;
int main()
{
    int n,k,x,i;
    char c;
    while(~scanf("%d%d",&n,&k)){
        multiset<int> a;
        for(i=1;i<=n;i++){
            getchar();
            scanf("%c",&c);
            if(c==‘I‘){
                scanf("%d",&x);
                a.insert(x);
                if(a.size()>k) a.erase(a.begin());
            }
            else printf("%d\n",*a.begin());
        }
    }
    return 0;
}

The kth great number multiset应用（找第k大值）

原文：http://www.cnblogs.com/yzm10/p/7224375.html