POJ - 1521/HDU-1053 Entropy

SunnyYuan的博客 / 2024-08-10 / 原文

题意

将每个字符串哈夫曼编码，输出 ASCII 需要位数、哈夫曼编码所需位数、压缩率。

思路

建哈夫曼树，将每个字符编码，然后再对应回去。

代码

注意处理只有一种字母的情况。

~~POJ 要改一堆乱七八糟的东西。~~

这个代码可以在 HDU 通过。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using PII = pair<int, int>;

const int N = 300;

string s;
unordered_map<char, int> mp;
priority_queue<PII, vector<PII>, greater<PII>> q;
int ch[N][2], ans[N], idx;

void dfs(int u, int x) {
    ans[u] = x;
    if (ch[u][0]) dfs(ch[u][0], x + 1);
    if (ch[u][1]) dfs(ch[u][1], x + 1);
}

void solve() {
    mp.clear();
    while (q.size()) q.pop();
    memset(ch, 0, sizeof(ch));
    memset(ans, 0, sizeof(ans));
    idx = 128;

    int n = s.size();
    for (auto x : s) mp[x]++;
    for (auto x : mp) q.push({x.second, x.first});

    while (q.size() > 1) {
        auto a = q.top(); q.pop();
        auto b = q.top(); q.pop();
        idx++;
        ch[idx][0] = a.second;
        ch[idx][1] = b.second;
        q.push({a.first + b.first, idx});
    }
    dfs(idx, 0);
    for (int i = 0; i < N; i++) ans[i] = max(ans[i], 1);
    int sum = 0;
    for (auto x : s) sum += ans[x];
    cout << 8 * n << ' ' << sum << ' ' << 8.0 * n / sum << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << setprecision(1) << fixed;
    while (cin >> s && s != "END") solve();
    return 0;
}