hdu 4006 The kth great number(优先队列)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4006

题目大意：

　　第一行输入 n k，后有 n 行，对于每一行有两种状态，①“I x” : 插入 x ② “Q” : 输出当前第 K大的数

解题思路：

　　利用优先队列保证插入新数据后的队列是有序的。

　　重点：保证 k 个数的队列就行。加一个标志 flag_k;

I:　　如果 flag_k<k,则将新输入的数放入队列中。

　　　否则判断第k个数是否小于新输入的数，如果小于,则队头出队，新输入的入队：保证队列中第k个数一直是最大的。

Q:　　输出队头即可。　

AC Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct Node
 4 {
 5     int key;
 6     friend bool operator < (Node a,Node b)
 7     {
 8         return a.key>b.key;
 9     }
10 };
11 int main()
12 {
13     int n,k;
14     while(scanf("%d%d",&n,&k)!=EOF)
15     {
16         priority_queue <Node> q;
17         int flag_k=0;
18         while(n--)
19         {
20             char c;
21             cin>>c;
22             if(c=='I')
23             {
24                 Node tem;
25                 scanf("%d",&tem.key);
26                 if(flag_k<k)
27                 {
28                     flag_k++;
29                     q.push(tem);
30                 }
31                 else
32                 {
33                     if(tem.key>q.top().key)
34                     {
35                         q.pop();
36                         q.push(tem);
37                     }
38                 }
39             }
40             else if(c=='Q')
41                 printf("%d
",q.top().key);
42         }
43     }
44     return 0;
45 }