POJ 1442 Black Box 优先队列题解

原题链接

Black Box

• 题意
• 输入一个数组num，长度M<=30000，输入一串数op，op[i]表示数组的前a[i]个数中第i大的数。下标均从1开始
• 存下数组，每次排序求出第i大的数，时间复杂度为O(MNlogM)，过高。
• 使用一个大顶堆，一个小顶堆，逐一读入一共a[i]个数并将其分配入堆中，使得大顶堆存的是最小的i个数，那么它的顶就是我们要求的输出；小顶堆是其余的数。在逐一读入过程中，先把数字放入小顶堆，若小顶堆顶比大顶堆顶小，那么交换，使得大顶堆中始终是最小的i个数。之后输出大顶堆的顶即可,要注意边界条件的判断。
• 由于每次将num数组中的数插入一个堆，时间复杂度为O(MlogM)，可以接受。
• 为了进一步优化避免超时，可以使用C++ STL自带的priority_queue来实现两种堆。
• 也可以手写树堆。
• AC代码如下

#include<iostream>
#include<queue>
#include<vector>
#define MAXM 30005
#define MAXN 30005
int num[MAXM] = { 0 };
int op[MAXN] = { 0 };
using namespace std;
template<class T>
class Greater {
public:
    bool operator()(const T& a, const T& b) {
        return a > b;
    }
};
priority_queue<int, vector<int>, less<int> > a;     //大顶堆
priority_queue<int, vector<int>, Greater<int> > b;  //小顶堆
int main() {
    int M, N;
    cin >> M >> N;
    for (int i = 1; i <= M; i++) {
        cin >> num[i];
    }
    for (int i = 1; i <= N; i++) {
        cin >> op[i];
    }
    int cnt = 0;
    int cursor = 1;
    while (cnt < M) {
        cnt++;
        b.push(num[cnt]);
        if (a.empty()) {//初始化
            a.push(b.top());
            b.pop();
        }
        else if (!b.empty() && a.top() > b.top()) {
            int t = a.top();
            a.pop();
            a.push(b.top());
            b.pop();
            b.push(t);
        }
        while (cursor<=M&&op[cursor] == cnt) {//输出时刻
            cursor++;
            cout << a.top() << endl;
            if (!b.empty()) {
                a.push(b.top());
                b.pop();
            }
            else {
                cnt++;
                a.push(num[cnt]);
            }
        }
    }
}