文章
10
粉丝
165
获赞
7
访问
25.7k
#include<bits/stdc++.h>
using namespace std;
string str;
int len, num[30];
int bfs() {
priority_queue<int, vector<int>, greater<int> > q; // 创建优先队列,从小到大排序
for(int i = 0; i < 30; i++) {
if(num[i]) q.push(num[i]); // 放入每个字母的个数
}
int sum = 0;
if(q.size() == 1) sum = q.top(); // 如果只有一个字母,直接等于该字母的数量
while(q.size() > 1) { // 得到前两个最小的叶子节点,将和放入队列中
int a = q.top(); q.pop();
int b = q.top(); q.pop();
sum += (a + b); q.push(a + b); // 因为ans累加了之前的值,所以传入的是a + b而非ans;
}
return sum;
}
int main() {
while(cin >> str) {
memset(num, 0, sizeof num);
if(str == "END") break; // 注意为双引号
len = str.size(); // 得到string类型的长度
for(int i = 0; i < len; i++) {
if(str[i] == '_') num[26]++; // 应为'A' - 'A'等于0,从下标0开始,所以'_'就在num[26]
else num[str[i] - 'A']++;
}
int res = bfs();
printf("%d %d %.1lf\n", len * 8, res, len * 8.0 / res);
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发