付翔的专栏 在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
`这次写代码基本也是一气呵成　，当然中间还是调试了才正确运行　，可以通过北邮ＯＪ　的测试　，其逻辑和在图书馆写在草稿的逻辑没有多大改动，看来写代码之前`
`做初步分析还是很重要的　，　`
`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;
}

}

/*

*/
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);

}

}
}

/*

*/
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));

}```
posted on 2011-03-16 15:44 付翔 阅读(261) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

 只有注册用户登录后才能发表评论。 相关文章:

 < 2011年3月 >
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

•