#include <iostream>
using namespace std;

const int MAX = 20001;
const int hufnum = 40002;
const int maxint = 60000;
int n;
int blanks[MAX];
__int64 sum;

typedef struct node
{
	int weight;
	int lchild;
	int rchild;
	int parent;
}huftree;
huftree tree[MAX*2];

void creattreehufman() 
{
	int i,j,p1,p2;
	float least1,least2;
	
	for(i = 1; i <= n * 2; i++)   
	{
		tree[i].parent = 0;
		tree[i].lchild = 0;
		tree[i].rchild = 0;
		tree[i].weight = 0;
	}

	for(i = 1; i <= n; i++)
	{
		tree[i].weight = blanks[i];
	}
	
	
	for(i = n + 1 ; i < n * 2 ; i++)  
	{
		p1 = 0;
		p2 = 0;
		least1 = maxint;     
		least2 = maxint;
		for(j = 1; j < i; j++)   
		{
			if(tree[j].parent == 0)  
			{
				if(tree[j].weight < least1)
				{
					least2 = least1;   
					least1 = tree[j].weight;
					p2 = p1;
					p1 =j;
				}
				else
				{
					if(tree[j].weight < least2)
					{
						least2 = tree[j].weight;   
						p2 = j;
					}
				}
			}
		}
		tree[p1].parent = i;            
		tree[p2].parent = i;
		tree[i].lchild = p1;          
		tree[i].rchild = p2;           
		tree[i].weight = tree[p1].weight + tree[p2].weight;  
 		sum += tree[i].weight;
	}
	tree[2*n - 1].parent = 0;   
}

int main()
{
	int i,j;
	while(cin>>n)
	{
		sum = 0;
		for(i = 1; i <= n; i++)
		{
			cin>>blanks[i];
		}
		creattreehufman();
		cout<<sum<<endl;
	}
	return 0;
}

• 我的也是用哈夫曼WA了， (1265) taishi 2010-03-17 13:30:41