HDU 4006 The kth greater number【优先级队列priority_queue】
程序员文章站
2024-02-14 23:51:22
...
这道题告诉你,给n个数,和1个数K,给你8次请求,有增加,也有提问第k个最大的数。
1. 方法一:(TLE超时),很显然数据量很大,1e6,快排O(nlogn),也有点悬。受不了。
#include <iostream>
#include <algorithm>
using namespace std;
int a[1000005];
int main() {
int n, k, x;
cin >> n >> k;
char op;
int cnt = 0;
for(int i = 0; i < n; i++) {
cin >> op;
if(op == 'I') {
cin >> a[cnt++];
} else {
sort(a, a + cnt, greater<int>());
cout << a[k - 1] << endl;
}
}
return 0;
}
后来想到了堆,(STL用优先级队列表示),priority_queue。默认是最大堆(priority_queue<int, vector<int>, less<int>())
这里应该是用最小堆, (即根一定大于等于左右字数的值)。
思路如下:
2. 方法二:(用优先队列priority_queue)
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int main() {
int n, k, x;
while(cin >> n >> k) {
while(!pq.empty()) pq.pop();
char op;
for(int i = 0; i < n; i++ ) {
cin >> op;
if(op == 'I') {
cin >> x;
if(pq.size() < k) {
pq.push(x);
} else {
if(x > pq.top()) {
pq.pop();
pq.push(x);
}
}
} else if (op == 'Q'){
cout << pq.top() << endl;
}
}
}
return 0;
}
AC啦。
Note:
1. priority_queue默认是最大堆 (priority_queue<int> pq 相当于 priority_queue<int , vector<int> , less<int> ())
最小堆是( priority_queue<int, vector<int>, greater<int>() )
2. 优先级队列常用函数:
C++ Priority Queues(优先队列)
C++优先队列类似队列,但是在这个数据结构中的元素按照一定的断言排列有序。
empty() | 如果优先队列为空,则返回真 |
pop() | 删除第一个元素 |
push() | 加入一个元素 |
size() | 返回优先队列中拥有的元素的个数 |
top() | 返回优先队列中有最高优先级的元素 |
上一篇: C# 获取当前月份天数的三种方法总结
下一篇: c#之用户定义的数据类型转换介绍