首页 > 代码库 > hdu 4006 The kth great number(优先队列)
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 else32 {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\n",q.top().key);42 }43 }44 return 0;45 }
hdu 4006 The kth great number(优先队列)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。