首页 > 代码库 > hdu 4006 The kth great number （优先队列）
hdu 4006 The kth great number （优先队列）
优先队列头文件
#include <queue>
默认优先为从大到小优先。
自定义优先级
1 struct cmpmin{ //按从小到大 2 3 // 因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。 4 bool operator ()(int &a, int &b){ 5 return a>b; //所以规定小的元素的优先级大于大的元素。 6 } 7 }; 8 9 struct cmpmax{ //按从大到小 10 bool operator ()(int &a, int &b){11 return a<b; 12 }13 };14 15 16 //多个元素的时候 17 struct node{ 18 int x, y;19 friend bool operator <(int a, int b){ //小的优先级小，所以按照x从大到小，注意默认是<来确定优先级。 20 return a.x < b.x;21 }22 }23 24 struct node{25 int x, y;26 friend bool operator <(int a, int b){ //小的优先级大，所以按照x从小到大 27 return a.x > b.x; 28 }29 }
本题要输出第K大的数，因为数据量大，不能每次排序，所以用优先队列来解决。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 struct cmp{ 7 bool operator ()(int &a,int &b){ 8 return a>b;//最小值优先 9 }10 };11 int n, k, val, cnt;12 char c;13 int main(){14 while(~scanf("%d%d", &n, &k)){15 cnt = 0;16 priority_queue <int, vector<int>,cmp> q;17 while(n--){18 cin>>c;19 if(c == ‘Q‘){20 printf("%d\n", q.top());21 }22 else if(c == ‘I‘){23 scanf("%d", &val);24 if(cnt < k){25 q.push(val);cnt++;26 }27 else{28 if(val > q.top()){29 q.pop();30 q.push(val);31 }32 }33 }34 }35 36 }37 38 39 return 0;40 }
hdu 4006 The kth great number （优先队列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。