欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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>())

这里应该是用最小堆, (即根一定大于等于左右字数的值)。

思路如下:

HDU 4006 The kth greater number【优先级队列priority_queue】

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啦。

HDU 4006 The kth greater number【优先级队列priority_queue】

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() 返回优先队列中有最高优先级的元素