您现在的位置是:首页 > 正文

HDU 4006 The kth great number(优先队列)

2024-02-01 01:47:34阅读 2

由于只有插入操作,所以不很复杂的数据结构,优先队列就可以了,每次保持队列中有k个元素,这样取出的头必然是第k大

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int n, k;

int main() {
    while (~scanf("%d%d", &n, &k)) {
        char s[2];
        int x;
        priority_queue<int, vector<int>, greater<int> > Q;
        while (n--) {
            scanf("%s", s);
            if (s[0] == 'I') scanf("%d", &x), Q.push(x);
            else {
                while (Q.size() > k) Q.pop();
                printf("%d\n", Q.top());
            }
        }
    }
    return 0;
}


网站文章