对顶堆用于维护序列的第 $ k $ 大元素, 原理是：建立一个小根堆和一个大根堆, 小根堆存储序列的前 $ k $ 大元素, 大根堆存储其他元素; 要取的第 $ k $ 大元素即是小根堆的堆顶, 维护的做法是：在查询之前, 保证小根堆的大小为 $ k $, 若有多余, 将多余部分转移到大根堆中, 否则, 从大根堆转移若干元素, 直到小根堆大小为 $ k $。
思路：对于此题, 当 $ i $ 为奇数时, 需要回答第 $ (i + 1) / 2 $ 大元素, 则, 在此时调整堆的大小即可。
点击查看代码
#include <bits/stdc++.h>
#define sz(a) ((int) (a).size())
using i64 = long long;
inline i64 read() {
bool sym = false; i64 res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main() {
int n = read(); std::vector<int> a(n + 1);
std::priority_queue<int, std::vector<int>, std::greater<int>> qmin;
std::priority_queue<int, std::vector<int>, std::less<int>> qmax;
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (int i = 1; i <= n; i++) {
if (qmin.empty() || a[i] >= qmin.top()) {
qmin.push(a[i]);
} else {
qmax.push(a[i]);
}
if (i & 1) {
int k = (i + 1) / 2;
while (qmin.size() > k) {
qmax.push(qmin.top()); qmin.pop();
}
while (qmin.size() < k) {
qmin.push(qmax.top()); qmax.pop();
}
printf("%d\n", qmin.top());
}
}
return 0;
}