POJ - 1442 Black Box解题报告（求第k小的数）

给你一个空的集合。两种操作，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;		}	}}