The kth great number（小根堆思想，模板题）

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

题目就是要求我们计算第k大的数，所以我们可以用小根堆的思想；

我们一直保持堆里面由有k个数，那么第k大的数就是堆顶，且一直更新堆，最后更新所有的数之后，我们就可以把堆顶输出 ，就是答案。

听懂了记得给个赞鼓励一下，码字不易，用爱发电。

上ac代码。

有事你就q我；QQ2917366383

学习算法

  #include<cstdio>
  #include<cstdlib>
  #include<cstring>
  #include<queue>
  #include<iostream>
  #include<algorithm>
  using namespace std;
  int main()
  {
    int n,k,a;
    while(scanf("%d%d",&n,&k)!=EOF)//多组数据输入不影响 
    {
      priority_queue<int ,vector<int>,greater<int> >q; //小根堆，小到大 
      int c=0;//标记堆里面元素个数 
      for(int i=0;i<n;i++)
      {
        char b;
        cin>>b;//输入判断的字符 
        if(b=='I')
        {
          if(c<k)
          {
            scanf("%d",&a);//输入数字 
            c++;
            q.push(a);//放进堆里面 
          }
          else if(c>=k)//如果超过或者等于第k个数 
          {
            scanf("%d",&a);//输入数字
            if(a>q.top())//比较后面输入的数是不是比前面第一个大， 
            {
              q.pop();//把第一个删掉
              q.push(a);//后面的数字放进 堆里面
            }
          }
        }
        else if(b=='Q')//结束条件 
        {
          printf("%d\n",q.top());//输出第一个 
        }
      }   
    } 
  }