Huffman 编码
时间限制:1.0s 内存限制:256.0MB
输入文件名:input.txt 输出文件名:output.txt
问题描述
输入一段文本,计算其中每一个字符的 huffman 编码,输出编码后文本的长度。
输入格式
输入数据包含一行,该行中的每个字符都是小写英文字母。
输出格式
输出仅有一行,包含 1 个数字,表示使用 huffman 编码后文本的长度。举例来说,原文是 aabcccc,如果对 a 用编码 00,对 b 用编码 01,对 c 用编码 1,那么编码后的文本应该是 0000011111,因此最后输出的数就是 10。
样例输入
adacatedecade
样例输出
29
数据规模和约定
输入数据的大小不超过 10KB,并且至少包含一个字符。
我的代码,全挂了
#include<bits/stdc++.h>
using namespace std;
string s;
int tmp,nd[35];
int table[30];
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt.txt","w",stdout);
cin>>s;
for(int i=0;i<s.size();i++)table[s[i]-'a']++;
for(int i=0;i<26;i++){
if (table[i]){
nd[++tmp]=table[i];
cout<<table[i]<<endl;
}
}
int cnt=0,ans=0;
sort(nd+1,nd+tmp+1);
for(int i=tmp;i>1;i--){
ans+=(++cnt)*nd[i];
//cout<<cnt<<"*"<<nd[i]<<endl;
}
ans+=cnt*nd[1];//cout<<cnt<<"*"<<nd[1]<<endl;
cout<<ans<<endl;
return 0;
}