HDU 1053 & HDU 2527 哈夫曼编码

http://acm.hdu.edu.cn/showproblem.php?pid=1053

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int a[];

char s[];

int cal(char x){

    if(x == '_') return ;

    else return x - 'A' + ;

}

struct node{

    int w;

    friend bool operator <(node aa, node bb){

        return aa.w > bb.w;

    }

};

int main(){

    while(~scanf("%s", s)){

        if(!strcmp(s,"END")) break;

        int len = strlen(s);

        memset(a, , sizeof(a));

        for(int i = ; i < len; i++){

            a[cal(s[i])]++;

        }

        priority_queue <node> q;

        for(int i = ; i < ; i++){

            node b;

            b.w = a[i];

            if(a[i]) q.push(b);

        }

        int res;

        if(q.size() == ) res = len;

        else{

            res = ;

            while(q.size() > ){

                int aa = q.top().w; q.pop();

                int bb = q.top().w; q.pop();

                res += (aa + bb);

                node b;

                b.w = aa + bb;

                q.push(b);

            }

        }

        printf("%d %d %.1lf\n", len*, res, len*8.0/res);

    }

    return ;

}

http://acm.hdu.edu.cn/showproblem.php?pid=2527

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int a[];

char s[];

int cal(char x){

    return x - 'a' + ;

}

struct node{

    int w;

    friend bool operator <(node aa, node bb){

        return aa.w > bb.w;

    }

};

int main(){

    int n;

    scanf("%d", &n);

    while(n--){

        int m;

        scanf("%d %s", &m, s);

        int len = strlen(s);

        memset(a, , sizeof(a));

        for(int i = ; i < len; i++){

            a[cal(s[i])]++;

        }

        priority_queue <node> q;

        for(int i = ; i < ; i++){

            node b;

            b.w = a[i];

            if(a[i]) q.push(b);

        }

        int res;

        if(q.size() == ) res = len;

        else{

            res = ;

            while(q.size() > ){

                int aa = q.top().w; q.pop();

                int bb = q.top().w; q.pop();

                res += (aa + bb);

                node b;

                b.w = aa + bb;

                q.push(b);

            }

        }

        if(res <= m) puts("yes");

        else puts("no");

    }

    return ;

}

两道几乎相同的题，哈夫曼编码的长度是合出来的各个节点之和（只剩一个节点停止），开始每个节点的权值是字符出现的频率，如果开始只有一个节点的情况要特判