這次寫代碼基本也是一氣呵成　，當然中間還是調試了才正確運行　，可以通過北郵ＯＪ　的測試　，其邏輯和在圖書館寫在草稿的邏輯沒有多大改動，看來寫代碼之前

做初步分析還是很重要的　，　

http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1817　

# include<stdio.h>
# include<stdlib.h>
# include<string.h>

const int N = 2*1000+ 3 ;

# define GetMax(a,b) ((a)>(b) ?(a) :(b) )
struct TreeNode
{
	int data;
	int left,right,father;
	int deep;
};

struct TreeNode ArrayTree[N];
int used[N];

int cmp(const void * a,const void * b)
{
	return ((struct TreeNode * )a)->data - ((struct TreeNode * )b)->data;
}
void init()
{
	memset(ArrayTree,0,sizeof(ArrayTree));
	memset(used,0,sizeof(used));
	for(int i = 0 ; i < N; i ++)
	{
		ArrayTree[i].deep = 1;
		ArrayTree[i].left = -1;
		ArrayTree[i].right = -1;
	}

}

/* 
用一維數組模擬樹的建立  前面end 是排好序的節點 ，也就是之后建好樹的葉子節點
以 0 -end -1 和 end - end2 -1  ,后面是編碼過程中形成的節點
我認為 最小的節點值  是來自兩段數組中 未使用的最前面的節點中最小的 


*/
int GetMinTreeNode(int end ,int end2) // 這里還可以優化 
{
	int i = 0,min1 = 0 ,min2 =end - 1,min;
	for(i = 0 ; i < end2 ; i ++) 
	{
		if(used[i] == 0)
		{
			min1 = i ;
			break;
		}
	}
	for(i = end ; i < end2 ; i ++)
	{
		if(used[i] == 0)
		{
			min2 = i ;
			break;
		}
	}
	//min = min1 < min2 ?min1 :min2;
	//if
	if(ArrayTree[min1].data < ArrayTree[min2].data)
		min = min1;
	else 
		min = min2;
	used[min] = 1;
	return min;

}
void updataTreeNode(int father ,int deep)
{
	int left = ArrayTree[father].left;
	int right = ArrayTree[father].right;
	if(father >= 2)
	{
		if(left != -1)
		{
			ArrayTree[left].deep = deep -1;
			updataTreeNode(left,deep-1);
		}
		if( right != 1 )
		{
			ArrayTree[right].deep = deep -1;
			updataTreeNode(right,deep-1);

		}

	}
}

/* 
用一維數組模擬樹的建立 
先排序 后根據哈弗曼算法 開始 建立樹 這里我根節點deep 有最大值 ，然后子節點一次遞減 

*/
void Hafuman( int end )
{
	qsort(ArrayTree,end,sizeof(struct TreeNode),cmp);
	
	int i,mend = end;
	struct TreeNode tNode;
	for( i = 0 ; i < end -1; i ++)
	{
		tNode.left = GetMinTreeNode(end,end + i) ;
		tNode.right = GetMinTreeNode(end,end + i);
		ArrayTree[tNode.left].father = ArrayTree[tNode.right].father = end + i;
		tNode.data = 	ArrayTree[tNode.left].data  + ArrayTree[tNode.right].data;
		tNode.deep = GetMax(ArrayTree[tNode.left].deep ,ArrayTree[tNode.right].deep ) + 1;
	//	updataTreeNode(end + i,	tNode.deep);//更新其子節點的深度值  這是一個bug 
		ArrayTree[end + i] = tNode;

		updataTreeNode(end + i,	tNode.deep);//更新其子節點的深度值 
		
	}
}
long GetHufuman(int end,int TreeDeep )
{
	int i,result = 0;
	for(i = 0 ; i < end ; i ++)
	{
		result += (TreeDeep - ArrayTree[i].deep )*ArrayTree[i].data;
	}
	return result;
}

int main()
{
	int end,i;
//	freopen("in.txt","r",stdin);
	scanf("%d",&end);
	
	init();
	for(i = 0 ; i < end ; i ++)
		scanf("%d",&ArrayTree[i].data);

	Hafuman(end);
	printf("%d\n",GetHufuman(end,ArrayTree[2*end-2].deep));
	
	
}