#include <stdio.h>

int n1,n2,n;

enum{
	MAX=5000001,
};

int data[MAX];

void HeapAdjust_MAX(int n,int target)
{
	int nChild;
	int nTemp;
	nTemp = data[target];
	
	while(2 * target <= n)
	{
		nChild = 2 * target;
		if(nChild + 1 <= n && data[nChild] < data[nChild + 1])
		{
			nChild++;//指向较大的孩子节点
		}
		if(nTemp < data[nChild])
		{
			data[target] = data[nChild];
			target = nChild;
		}
		else break;
	}
	data[target] = nTemp;
}
void HeapAdjust_MIN(int n,int target)
{
	int nChild;
	int nTemp;
	nTemp = data[target];
	
	while(2 * target <= n)
	{
		nChild = 2 * target;
		if(nChild + 1 <= n && data[nChild] > data[nChild + 1])
		{
			nChild++;
		}
		if(nTemp > data[nChild])
		{
			data[target] = data[nChild];
			target = nChild;
		}
		else break;
	}
	data[target] = nTemp;

}

int tmp;
static void inline swap(int x,int y)
{
	
	tmp = data[x];
	data[x] = data[y];
	data[y] = tmp;
}
void HeapSort_MAX(int n,int cnt)
{
	int i;
	//先对队列进行大顶堆排序
	for(i = n/2;i >= 1;--i)
		HeapAdjust_MAX(n,i);
	for(i = n;i >= n - cnt;--i)
	{
		swap(i,1);
		HeapAdjust_MAX(i - 1,1);
	}
}
void HeapSort_MIN(int n,int cnt)
{
	int i;
	for(i = n/2;i >= 1;--i)
		HeapAdjust_MIN(n,i);
	for(i = n;i >= n - cnt;--i)
	{
		swap(i,1);
		HeapAdjust_MIN(i - 1,1);
	}
}


int main()
{
	int i;
	double ans;
	long  long sum;
	freopen("input","r",stdin);
	while(scanf("%d %d %d",&n1,&n2,&n))
	{
		sum = 0;
		if(n1 == 0 || n2 == 0 || n == 0) break;
		for(i = 1;i <= n;++i)
		{
			scanf("%d",&data[i]);
			sum += data[i];
		}
		HeapSort_MAX(n,n1);//按大顶堆，队列后部分有序
		HeapSort_MIN(n - n1,n2);
		for(i = n;i > n - n1 -n2;--i)
			sum -= data[i];
		ans = (sum * 1.0)/(double)(n - n1 - n2);
		printf("%f\n",ans);
	}
	return 0;
}

• Re:为什么自己写的堆排序超出内存？？ (2021) 2013013121 2015-01-31 10:12:21