文章

61

粉丝

137

获赞

18

访问

38.3k

头像
哈夫曼编码 题解:c++优先队列实现,注意全为同一字符的特殊情况,例如:BBBBBBBBBB
P1562
发布于2024年3月25日 15:43
阅读数 551

#include<bits/stdc++.h>
using namespace std;

void func(string s){
    int len = s.size();
    set<char> myset;
    for(int i = 0; i < len ;i++)
        myset.insert(s[i]);
    //获得每种字符使用频率的优先队列
    priority_queue<int, vector<int>, greater<int>> pq;
    for(auto i = myset.begin(); i != myset.end(); ++i){
        int tmp = count(s.begin(), s.end(), *i);
        pq.push(tmp);
    }

    //计算WPL
    int wpl = 0;
    if(pq.size() == 1)
        wpl = len;
    while(pq.size() > 1){
        int tmp = pq.top();
        pq.pop();
        tmp += pq.top();
        pq.pop();
        pq.push(tmp);
        wpl += tmp;
    }

    printf("%d %d %.1f\n", len*8, wpl, len*8.0/wpl);
}


int main() {
    string s;
    while(cin >> s){
        if (s == "END")
            break;
        func(s);
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发