Posted on 2008-04-11 17:00
superman 阅读(275)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1117 C++ 00:00.00 840K */
2 #include <string>
3 #include <limits.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int cnt[27], len, ans;
9
10 struct
11 {
12 int w;
13 int left, right;
14 bool used;
15 }Tree[100];
16
17 void InOrder(int p, int n)
18 {
19 if(Tree[p].left)
20 InOrder(Tree[p].left, n + 1);
21 if(Tree[p].right)
22 InOrder(Tree[p].right, n + 1);
23 if(Tree[p].left == 0 && Tree[p].right == 0)
24 ans += Tree[p].w * n;
25 }
26
27 int main()
28 {
29 cout.setf(ios_base::showpoint);
30 cout.setf(ios_base::fixed);
31 cout.precision(1);
32
33 string s;
34 while(cin >> s && s != "END")
35 {
36 memset(cnt, 0, sizeof(cnt));
37 for(int i = 0; i < s.size(); i++)
38 if(s[i] == '_')
39 cnt[0]++;
40 else
41 cnt[s[i] - 'A' + 1]++;
42
43 len = 0;
44 for(int i = 0; i < 27; i++)
45 if(cnt[i])
46 {
47 len++;
48 Tree[len].w = cnt[i];
49 Tree[len].left = Tree[len].right = 0;
50 Tree[len].used = false;
51 }
52
53 while(true)
54 {
55 int m1 = INT_MAX, m2 = INT_MAX, idx1, idx2;
56
57 for(int i = 1; i <= len; i++)
58 if(Tree[i].used == false)
59 if(m1 > Tree[i].w)
60 {
61 m1 = Tree[i].w;
62 idx1 = i;
63 }
64 if(m1 == INT_MAX) break;
65 Tree[idx1].used = true;
66
67 for(int i = 1; i <= len; i++)
68 if(Tree[i].used == false)
69 if(m2 > Tree[i].w)
70 {
71 m2 = Tree[i].w;
72 idx2 = i;
73 }
74 if(m2 == INT_MAX) break;
75 Tree[idx2].used = true;
76
77 len++;
78 Tree[len].w = m1 + m2;
79 Tree[len].left = idx1;
80 Tree[len].right = idx2;
81 Tree[len].used = false;
82 }
83
84 if(len == 1)
85 ans = s.size();
86 else
87 {
88 ans = 0;
89 InOrder(len, 0);
90 }
91
92 cout << 8 * s.size() << ' ' << ans << ' '
93 << double(8 * s.size()) / ans << endl;
94 }
95
96 return 0;
97 }
98