用堆来做的，用了两个堆，最大堆和最小堆
#include<stdio.h>
//using namespace std;
int a[1000011];//数组数据
struct Heap
{
	int x;
	int ID;
};
Heap D[1000011];//最大堆
Heap X[1000011];//最小堆

int DL[1000011];//DL[i]表示数组a[i]在D中的下标
int XL[1000011];//XL[i]表示数组a[i]在X中的下标

int OutMin[1000011];//最小值
int OutMax[1000011];//最大值

int n,k;
void HeapAdjust(Heap H[] ,int s,int m,int L[],bool isMax)
{
	Heap rc=H[s];
	int j;
	for(j=s*2;j<=m;j*=2)
	{
		if(isMax)
		{		
			if(j<m && H[j].x<H[j+1].x)
				j++;
			if(rc.x>H[j].x)break;
			H[s]=H[j];
			L[H[s].ID]=s;
			s=j;
		}
		else
		{
			if(j<m && H[j].x>H[j+1].x)
				j++;
			if(rc.x<H[j].x)break;
			H[s]=H[j];
			L[ H[s].ID]=s;
			s=j;
		}
	}
	H[s]=rc;
	L[H[s].ID]=s;

}
void MakeHeap(Heap H[],int length,int L[],bool isMax)
{
	for(int i=length/2;i>0;--i)
	{
		HeapAdjust(H,i,length,L,isMax);
	}
}
int main()
{
	int i;
	scanf("%d%d",&n,&k);
	if(k>n)
		k=n;
	for(i=1;i<=k;++i)
	{
		scanf("%d",&a[i]);

		D[i].x=a[i];
		D[i].ID=i;
		DL[i]=i;

		X[i].x=a[i];
		X[i].ID=i;
		XL[i]=i;
	}
	for(i=k+1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	MakeHeap(D,k,DL,true);
	MakeHeap(X,k,XL,false);
	OutMax[0]=D[1].x;
	OutMin[0]=X[1].x;
	for(i=k+1;i<=n;++i)
	{		
		int j;
		int d=DL[i-k];
		D[d].x=a[i];
		D[d].ID=i;
		DL[i]=d;
		j=d > k/2 ? k/2 : d;
		for(;j>0;j/=2)
		{
			HeapAdjust(D,j,k,DL,true);
		}

		int dd=XL[i-k];
		X[dd].x=a[i];
		X[dd].ID=i;
		XL[i]=dd;
		j=dd > k/2 ? k/2 : dd;
		for(;j>0;j/=2)
		{
			HeapAdjust(X,j,k,XL,false);
		}
		
		OutMax[i-k]=D[1].x;
		OutMin[i-k]=X[1].x;

	}
	for(i=0;i<=(n-k);++i)
	{
		printf("%d%c", OutMin[i], (i < n - k) ? ' ' : '\n'); 

	}
	for(i=0;i<=(n-k);++i)
	{
		printf("%d%c", OutMax[i], (i < n - k) ? ' ' : '\n'); 
	}
	return 0;
}

• Re:老是WA，有没有高手知道原因？极度郁闷中。。。。。 (1824) brightstar5 2010-04-05 19:50:53