输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。
输出权值。
5 1 2 2 5 9
37
#include<stdio.h> struct tree { int weight; int left; int right; int parent; int car; //1表明该节点要加入计算 }; void insert(int y[],struct tree haf[],int z){ int a,min1=100000000,min2=100000000,count1,count2; for(int i=0;i<2000;i++){ if(y[i]<min1&&y[i]!=-1){ min1=y[i]; count1=i; } } y[count1]=-1; for(int i=0;i<2000;i++){ if(y[i]<min2&&y[i]!=-1){ min2=y[i]; count2=i; } } y[count2]=-1; a=min1+min2; y[z]=a; haf[z].weight=a; haf[z].left=count1; haf[z].right=count2; haf[count1].parent=z; haf[count2].parent=z; return; } void cal(int sum1[],struct tree haf[],int head,int e){ if(haf[head].car==1){ sum1[0]=sum1[0]+e*haf[head].weight; } if(haf[head].left!=-1){ cal(sum1,haf,haf[head].left,e+1); } if(haf[head].right!=-1){ cal(sum1,haf,haf[head].right,e+1); } return; } int main(){ int b,n,m[2000],count,sum[1],k=0,x=0; struct tree haff[2000]; for(int i=0;i<2000;i++){ haff[i].left=-1; haff[i].right=-1; haff[i].parent=-1; haff[i].car=-1; haff[i].weight=-1; m[i]=-1; } scanf("%d",&n); for(b=0;b<n;b++){ int j; scanf("%d",&j); m[b]=j; haff[b].weight=j; haff[b].car=1; } //case1:这个方法和下面的while方法应该都可以的 /*for(int i=0;i<n-1;i++){ insert(m,haff,b); b++; }*/ while(x!=2){ x=0; for(int i=0;i<2000;i++){ if(m[i]!=-1) x++; } insert(m,haff,b); b++; } for(int i=0;i<2000;i++){ if(m[i]!=-1){ count=i; break; } } sum[0]=0; cal(sum,haff,count,k); printf("%d",sum[0]); return 0; }
//哈夫曼树理解题意:每次选出最小的,然后重新加入,first可以用vector然后每次都进行排序 //最好的办法是运用priority_queue #include <cstdio> #include <iostream> #include <queue> using namespace std; int main(){ int n; cin>>n; priority_queue<int,vector<int>,greater<int>> myq; while(n--){ int x; cin>>x; myq.push(x); } int ans=0; while(myq.size()>1){ int a=myq.top(); myq.pop(); int b=myq.top(); myq.pop(); ans+=a+b; myq.push(a+b); } printf("%d\n",ans); return 0; }
//实际上,可以用数组,然后每次都进行排序 #include <stdio.h> #include <math.h> #include <stdlib.h> int cmp(const void* a,const void* b){ return *(int*)b-*(int*)a; } int main(){ int n; scanf("%d",&n); int num[1000]; for(int i=0;i<n;i++){ scanf("%d",&num[i]); } qsort(num,n,sizeof(num[0]),cmp); int sum=0,i; for(i=n-1;i>0;i--){ int a=num[i]; int b=num[i-1]; num[i-1]=a+b; sum+=num[i-1]; qsort(num,i,sizeof(num[0]),cmp); } printf("%d\n",sum); return 0; }