一行实现哈弗曼权值计算

一行实现哈弗曼权值计算

杭电1053

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}