hdu 2527哈夫曼树（二叉树的运用）

#include<stdio.h>

#include<string.h>

#define N 100

#define INF 2000000000

int b[N];

char s[100001];

struct nodee{

int parent,lson,rson,visit,weight;

}a[N];

int main() {

int t,n,m,count,i,j,max1,max2,total,sum;

scanf("%d",&t);

while(t--) {

scanf("%d",&total);

scanf("%s",s);

count=0;

memset(b,0,sizeof(b));

for(i=0;s[i];i++)

b[s[i]-'a']++;

j=1;

for(i=0;i<26;i++)

if(b[i]) {

a[j].lson=a[j].rson=a[j].parent=a[j].visit=0;

a[j].weight=b[i];

j++;

}

count=j-1;

for(i=1;i<count;i++) {//creat 哈夫曼树

max1=max2=INF;

n=m=0;

for(j=1;j<count+i;j++) {

if(!a[j].visit&&a[j].weight<max1) {

m=n;

max2=max1;

n=j;

max1=a[j].weight;

}

else

if(!a[j].visit&&a[j].weight<max2) {

m=j;

max2=a[j].weight;

}

}

a[count+i].weight=a[n].weight+a[m].weight;

a[count+i].lson=n;

a[count+i].rson=m;

a[count+i].visit=0;//这个要初始化，不然不对

a[n].parent=count+i;

a[m].parent =count+i;

a[n].visit=1;

a[m].visit=1;

}

sum=0;

for(i=count+1;i<=count*2-1;i++)//相当于求所有叶节点的带权路径长度

sum+=a[i].weight;

if(count==1)

sum=a[1].weight;

if(sum<=total)

printf("yes\n");

else

printf("no\n");

}

return 0;

}

巴特西

hdu 2527哈夫曼树（二叉树的运用）

最新文章

热门文章