//第一次写huffman,顺便学一下STL
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
//以下STL是参考过来的,再次感到STL的强大
class cmp
{
public:
bool operator()(int x,int y)
{
return x>y;
}
};
priority_queue<int ,vector<int>,cmp> Q;
int main()
{
char str[500];
while(gets(str))
{
if(!strcmp(str,"END"))break;
int len=strlen(str),i;
int c[200];
memset(c,0,sizeof(c));
for(i=0;i<len;i++)
c[str[i]]++;
for(i=0;i<200;i++)
if(c[i])
Q.push(c[i]),c[i]=0;
int sum=0;
if(Q.size()==1)sum=len;//要注意的一点,只有一种字母时sum为len
while(Q.size()>1)//队列的实现
{
int a=Q.top();Q.pop();
int b=Q.top();Q.pop();
sum+=a+b;
Q.push(a+b);
}
while(!Q.empty())
Q.pop();
printf("%d %d %.1lf\n",8*len,sum,(double)8*len/double(sum));
}
return 0;
}
分享到:
相关推荐
模拟题 要注意时间的处理 使用优先队列处理请求的事件 进行适当的运算符重载,可以简化代码
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
本篇文章是对优先队列+BFS进行了详细的分析介绍,需要的朋友参考下
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
NULL 博文链接:https://128kj.iteye.com/blog/1730484
POJ部分题解
很好很强大的POJ分类 新手+进阶+题目完全分类 赶快下载
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
西北工业大学POJ试题C++答案代码+课程设计
NULL 博文链接:https://128kj.iteye.com/blog/1750462
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
* 图的深度优先遍历和广度优先遍历:例如 poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最短路径算法:例如 Dijkstra、Bellman-Ford、Floyd、Heap+Dijkstra,例如 poj1860、poj3259、poj1062、poj...
北大POJ1159-Palindrome 解题报告+AC代码