給你一個空的集合。兩種操作，add(i)和get分別是把i加入到集合中去，將集合中的數從小到大排列，k++，然后輸出第k個(k一開始是0)。現在讓你按照他給出的流程瘋狂操作，并輸出每次get彈出的值。

最慘的情況就是add()和get操作各30000次。應該就是用一個堆吧，每次插入一個數需要logn，最慢就是不到nlogn，然后每次取出第k小的數需要klogn，取出操作最多不到n*n*logn。

然后無奈去網上查，用兩個堆，兩個。一個大頂堆，一個小頂堆，要求小頂堆的頂大于大頂堆。然后就是大頂堆里要有k個數，記大頂堆的頂為big，小頂堆的頂為small。(big<small)

綜合以上，時間復雜度O(nlogn)

#include<iostream>#include<stdio.h>#include<algorithm>#define N 30500using namespace std;int m,n;//m次輸入操作以及n次輸出操作 int a[N]={0};//要add的數 int b[N]={0};//第i個要get的次數為b[i]int big[N]={0};int small[N]={0};bool cmp(int x,int y){	return x>y;}void add(int x,int i,int k){	if(x>=big[0])//如果要插入的數大于大頂堆的頂，那么就把它插入小頂堆 	{		small[i-k-1]=x;		push_heap(small,small+i-k,cmp);	}	else//不然就把它插入大頂堆，大頂堆最大的數彈出，插到小頂堆里 	{		big[k]=x;		push_heap(big,big+k);		small[i-k-1]=big[0];		push_heap(small,small+i-k,cmp);		pop_heap(big,big+k+1);	}}void get(int i,int k){	PRintf("%d/n",small[0]);	big[k]=small[0];	push_heap(big,big+k+1);	pop_heap(small,small+i-k,cmp);}void ceshi(){	cout<<"big:   ";	for(int i=0;i<m;i++)	{		cout<<big[i]<<" "; 	}	cout<<endl;	cout<<"small: ";	for(int i=0;i<m;i++)	{		cout<<small[i]<<" "; 	}	cout<<endl;}int main(){	cin>>m>>n;	for(int i=1;i<=m;i++)	{		scanf("%d",&a[i]);	}	for(int i=1;i<=n;i++)	{		int l;		scanf("%d",&l);		b[l]++;	}	int k=0;//最大堆里面的數的個數		for(int i=1;i<=m;i++)	{		add(a[i],i,k);		//ceshi();		while(b[i]!=0)		{			get(i,k);			k++;			b[i]--;			//ceshi();cout<<endl;		}	}}