一行实现哈弗曼权值计算 | Patrick's Space

一行实现哈弗曼权值计算

杭电1053

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>

using namespace std;
#define INF 0x3fffffff
const int maxn = 10005;
int num[maxn];

bool cmp(int x, int y)
{
    return x > y;
}

int main()
{
    int n;
    string s;
    while(cin >> s)
    {
        map<char, int> a;
        if (s == "END")
            break;
        int len = s.size();
        for (int i = 0; i < len; ++i)
        {
            if (a.count(s[i]) == 0)
                a[s[i]] = 1;
            else
                a[s[i]]++;
        }
        int b = 0;
        for (map<char, int>::iterator it = a.begin(); it != a.end(); ++it)
        {
            num[b] = it->second;
            b++;
        }
        int l = a.size();
        sort(num, num + a.size(), cmp);
        int cnt = 0;
        for (int j = l - 1; j > 0; --j)  // 合并为只有一个元素，l - 1 次
        {
            // 哈弗曼树
            // 取了最小的两个数
            num[j - 1] += num[j];
            // 越小的元素等效加的次数越多
            cnt += num[j - 1];
            // 更新新树，把最后一个元素也抛弃了
            // 相当于把最小的两个元素都抛弃了
            sort(num, num + j, cmp);
        }
        if (l == 1)
            printf("%d %d %.1f\n", 8 * len, num[0], (8 * len + 0.0)/num[0]);
        else
            printf("%d %d %.1f\n", 8 * len, cnt, (8 * len + 0.0)/ cnt);
    }
    return 0;
}