Luogu P1801 黑匣子

题目描述

https://www.luogu.com.cn/problem/P1801

加入一个元素

输出第 $i$ 小的元素，$i$ 依次递增

Solution

堆的经典用法之一，我们维护一个大根堆和一个小根堆，大根堆代表前 $i$ 小

每次如果小根堆的堆顶小于大根堆的堆顶，我们就应该把这个元素换到大根堆中

#include <iostream>
#include <cstdio>
#include <queue>
#define maxn 200010
using namespace std;

int n, m, a[maxn], b[maxn];


priority_queue<int> Q1;
priority_queue<int, vector<int>, greater<int> > Q2; 

int main() { 
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i) scanf("%d", &b[i]); 
    int j = 0;
	for (int i = 1; i <= m; ++i) { 
		while (j + 1 <= b[i]) Q2.push(a[++j]);
		while (Q1.empty() || Q2.top() < Q1.top() || Q1.size() < i) {
			if (Q2.empty()) break;
			Q1.push(Q2.top()), Q2.pop();
		}
		while (Q1.size() > i) Q2.push(Q1.top()), Q1.pop();
		printf("%d\n", Q1.top());
	}       
    return 0;
}