A16 对顶堆 第k大的数

//这是70分代码
#include<bits/stdc++.h>
using namespace std;

int a[31100],u[31100];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&u[i]);
	int j=1;
	for(int i=1;i<=n;i++)
	{
		sort(a+1,a+i+1);
		
		while(j<=m && u[j]==i)
		{
			printf("%d\n",a[j]);
			j++;
		}
	}
	return 0;
}

//这是100分代码，但不是最快的，很容易被卡
#include<bits/stdc++.h>
using namespace std;

int a[31100],u[31100];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&u[i]);
	int j=1;
	for(int i=1;i<=n;i++)
	{
		//sort(a+1,a+i+1);
		for(int k=i;k>=2;k--)//插入排序
		{
			if(a[k]<a[k-1]) swap(a[k],a[k-1]);
			else break;
		}
		while(j<=m && u[j]==i)
		{
			printf("%d\n",a[j]);
			j++;
		}
	}
	return 0;
}

//100分程序，堆顶维护
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int a[N],b[N];
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int j=1;j<=m;j++) scanf("%d",&b[j]);
	sort(b+1,b+m+1);
	priority_queue<int,vector<int>,less<int>  > Q1;//大根堆 
	priority_queue<int,vector<int>,greater<int> > Q2;//小根堆 
	int j=1;
	for(int i=1;i<=n;i++)
	{
		//add操作 
		Q2.push(a[i]);
		if( !Q1.empty() && Q1.top()>Q2.top() )
		{
			int t=Q1.top();Q1.pop();
			Q2.push(t);
			t=Q2.top();Q2.pop();
			Q1.push(t);
		}
		
		while(j<=m && b[j]==i)//get操作 发生在i次add操作之后 
		{
			printf("%d\n",Q2.top());
			Q1.push(Q2.top());
			Q2.pop();
			j++;
		}	
	}
	return 0;
}