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 ;
}

最新文章

  1. linux命令:文件属性
  2. C语言 百炼成钢5
  3. access应用分享
  4. 前端学习-使用JS库Leaflet.js生成世界地图并获取标注地址经纬度。
  5. javascript中break和continue的区别
  6. zabbix_server---微信报警
  7. javascript数据类型及转换
  8. Servlet--取得初始化配置信息
  9. php 微信JS-SDK封装类
  10. 玩转spring MVC(七)----拦截器
  11. android学习笔记--Scanner
  12. Command &quot;python setup.py egg_info&quot; failed with error code 1 in C:\Users\w5659\AppData\Local\Temp\pip-install-t7uomu4r\xa dmin\
  13. Leetcode#521. Longest Uncommon Subsequence I(最长特殊序列 Ⅰ)
  14. (一)java基础
  15. python tcp .demo
  16. centos中nodejs npm安装cordova
  17. Shiro在Spring session管理
  18. elk6快速安装
  19. 基于注解的接口限流+统一session认证
  20. c#实现内存映射文件共享内存

热门文章

  1. linux下杀死进程(kill)的N种方法 【转】
  2. php代码优化技巧
  3. 转 sqlserver字段描述相关操作sql
  4. CSS Clip剪切元素实例
  5. equals函数的作用
  6. ORACLE 数据库简单测试
  7. SGU 142.Keyword
  8. SGU 226.Colored graph(最短路)
  9. 用jq 做了一个排序
  10. MVC 文本转换成html显示