#include "stdio.h"
#include "stdlib.h"
#define Swap(a,b) a=a+b;b=a-b;a=a-b
void Shift(__int64 *heap,int j,int n)
{
	int i;
	int MinSon;
	heap[0]=heap[j];
	for(i=j;i<=n/2;)
	{
		MinSon=i*2;
		if(MinSon!=n&&heap[MinSon]>heap[MinSon+1])
		{
			MinSon++;
		}
		if(heap[i]>heap[MinSon])
		{
			heap[i]=heap[MinSon];
			i=MinSon;
			heap[i]=heap[0];
		}
		else break;
	}
	heap[i]=heap[0];
}
void Insert(__int64 *heap,__int64 x,int n)
{
	heap[n]=x;
	for(int i=n;i/2>0;i=i/2)
	{
		if(heap[i]<heap[i/2])
		{
			Swap(heap[i],heap[i/2]);
		}
	}

}
void Minheap(__int64 *heap,int n)
{
	int i;
	for(i=n/2;i>0;i--)
	{
		Shift(heap,i,n);
	}
}
__int64 MinCost(__int64 *heap,int n)
{
	__int64 sum=0;
	Minheap(heap,n);
	for(int i=n;i>1;i--)
	{
		if(i==2)
		{
			sum+=heap[1]+heap[2];
			break;
		}
		Swap(heap[1],heap[i]);
		Shift(heap,1,i-1);
		Swap(heap[1],heap[i-1]);
		Shift(heap,1,i-2);
		sum+=heap[i]+heap[i-1];
		Insert(heap,heap[i]+heap[i-1],i-1);
	}
	return sum;
}
int main()
{
	int n;
	__int64 *heap;
	scanf("%d",&n);
	heap=(__int64 *)malloc((n+1)*sizeof(__int64));
	heap[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d",heap+i);
	}
	printf("%I64d\n",MinCost(heap,n));
	return 0;
}

• 赞！！！顶一个,以所给的木板长度为叶子结点构造哈夫曼树，最少钱数为所有非叶子结点的和。 (1410) gfedcba 2009-03-06 12:19:15
• Re:我的ac代码，纯c 16ms 共同学习 (47) sunkehappy 2009-03-15 15:24:58
  • 好长~~ (815) zjut020 2009-03-26 11:11:54
    • Re:好长~~ (51) majia8 2009-04-25 19:53:00
      • 晕倒，。。没细看他的代码 (5) zjut020 2009-05-03 22:39:15