对顶堆
$O(mnlogn)$
用一个大顶堆维护前k - 1个数,剩余的数用小顶堆维护,这样就可以从小顶堆上取出排序后的第k位数
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 30010;
int ADD[N];
int GET[N];
//用大顶堆维护前k - 1个最小的元素,用小顶堆维护剩余的元素
priority_queue<int, vector<int>, greater<int>> minhp;
priority_queue<int> maxhp;
int n, m, k;
int main(){
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &ADD[i]);
for(int i = 0; i < m; i++){
int x;
scanf("%d", &x);
GET[x]++;
}
k = 1;
for(int i = 0; i < n; i++){
if(minhp.empty() || ADD[i] < minhp.top()) maxhp.push(ADD[i]);
else minhp.push(ADD[i]);
while(maxhp.size() != k - 1){
if(maxhp.size() > k - 1){
int p = maxhp.top(); maxhp.pop();
minhp.push(p);
}
else{
int p = minhp.top(); minhp.pop();
maxhp.push(p);
}
}
while(GET[i + 1]--){
printf("%d\n", minhp.top());
int p = minhp.top(); minhp.pop();
maxhp.push(p);
k++;
}
}
return 0;
}