Entropy (huffman) 优先队列)
2024-08-26 06:35:37
http://acm.hdu.edu.cn/showproblem.php?pid=1053
Huffman问题利用STL中的priority_queue解决;
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
using namespace std; struct cmp
{
bool operator()(const int a, const int b)
{
return a > b;
}
};
int solve(string str)
{
priority_queue< int,vector<int>,cmp >que;
map<char, int> mymap;
int i;
for(i =; i < str.size(); i++)
{
mymap[str[i]]++;
} map<char,int>::iterator it = mymap.begin();
while(it != mymap.end())
{
//printf("%c %d\n",it->first,it->second);
que.push(it->second);
it++;
} int weight = ;
if(que.size() == )
return que.top(); while(que.size() != )
{
int a,b;
a = que.top();
que.pop();
b = que.top();
que.pop(); weight += a+b;
que.push(a+b);
}
return weight;
}
int main()
{
int weight;
string str;
while(cin>>str)
{
if(str == "END")
break;
weight = solve(str);
printf("%d %d %.1lf\n",*str.size(),weight,8.0*str.size()/weight);
}
return ;
}
最新文章
- linux命令:文件属性
- C语言 百炼成钢5
- access应用分享
- 前端学习-使用JS库Leaflet.js生成世界地图并获取标注地址经纬度。
- javascript中break和continue的区别
- zabbix_server---微信报警
- javascript数据类型及转换
- Servlet--取得初始化配置信息
- php 微信JS-SDK封装类
- 玩转spring MVC(七)----拦截器
- android学习笔记--Scanner
- Command ";python setup.py egg_info"; failed with error code 1 in C:\Users\w5659\AppData\Local\Temp\pip-install-t7uomu4r\xa dmin\
- Leetcode#521. Longest Uncommon Subsequence I(最长特殊序列 Ⅰ)
- (一)java基础
- python tcp .demo
- centos中nodejs npm安装cordova
- Shiro在Spring session管理
- elk6快速安装
- 基于注解的接口限流+统一session认证
- c#实现内存映射文件共享内存