【思路】
建立一个小堆和一个大堆。大堆用来存放第1..index-1大的数,其余数存放在大堆,小堆的堆顶元素便是我们要求出的第index大的数。每次插入一个A(n),必须保证大堆中数字数目不变,故先插入小堆中。若此时小堆堆顶小于大堆堆顶,则交换堆顶元素;每次Get(),输出小堆的堆顶元素,并将它并入大堆中。
【易错点】
Get()的While循环必须放在插入之后进行判断,否则若放在插入之前写作 while (j<N && u[j]==i),当不再插入A(n)时,剩下的Get()将不再执行,导致WA。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=;
int A[MAXN];
int u[MAXN];
int M,N; int main()
{
scanf("%d%d",&M,&N);
for (int i=;i<M;i++) scanf("%d",&A[i]);
for (int i=;i<N;i++) scanf("%d",&u[i]);
priority_queue< int,vector<int>,less<int> > maxHeap;//index..最后
priority_queue< int,vector<int>,greater<int> > minHeap;//1..index-1
int j=;
for (int i=;i<M;i++)
{
minHeap.push(A[i]);
if (!maxHeap.empty() && maxHeap.top()>minHeap.top())
{
int temp1=maxHeap.top();maxHeap.pop();
int temp2=minHeap.top();minHeap.pop();
maxHeap.push(temp2);
minHeap.push(temp1);
}
while (j<N && u[j]==i+)
{
cout<<minHeap.top()<<endl;
maxHeap.push(minHeap.top());
minHeap.pop();
j++;
}
}
return ;
}