Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么自己写的堆排序超出内存??

Posted by 2013013121 at 2015-01-31 10:12:21 on Problem 2833
In Reply To:为什么自己写的堆排序超出内存?? Posted by:sdau_085111 at 2013-04-04 19:58:32
> #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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator