题意分析

题目描述较长，其实意思就是输入一个字符串，分别用普通$ASCII$编码（每个字符$8bit$）和Huffman编码，输出编码后的长度，并输出压缩比。

解题思路

1.字符频率统计：对输入字符串进行排序后，通过遍历字符串比较相邻字符，统计每个字符的出现次数，将出现次数存储在优先队列中。这种方式可以方便后续构建哈夫曼树时，快速获取每个字符的频率信息。 2.哈夫曼树构建（利用优先队列）：哈夫曼树是一种用于实现最优前缀无关变长编码的树状结构，其核心思想是让出现频率高的字符使用更短的编码。代码中利用优先队列来模拟哈夫曼树的构建过程，优先队列中元素按从小到大的顺序排列（greater）。每次从优先队列中取出两个最小的频率值（代表两个节点），将它们合并为一个新的节点（频率为两者之和），并将新节点的频率值重新加入优先队列，重复此过程直到优先队列中只剩下一个元素，此时这个元素就是哈夫曼树的根节点的频率值。 3.编码长度计算：在构建哈夫曼树的过程中，每次合并两个节点时，将它们的频率之和累加到 Huff 变量中，最终 Huff 变量的值就代表了使用最优前缀无关变长编码时字符串所占用的比特数。对于只有一种字符的特殊情况，直接将字符出现次数作为编码长度。

C++代码实现

cpp

#include<iostream>
#include<queue>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
	string s;
	priority_queue< int,vector<int>,greater<int> > Q;
	while(getline(cin,s)&&s!="END"){
		int t=1;
		sort(s.begin(),s.end()); //先排序，确保相同字符相邻 
		for(int i=0;i<s.length();i++){
			if(s[i]!=s[i+1]){
				Q.push(t);
				t=1;
			}
			else{
				++t;
			}
		}//统计每个字符出现的频次，并放进优先队列 
		
		int ans=0;//ans为Huffman编码总长度 
		if(Q.size()==1) ans=Q.top();//不要忘了只有1个的情况 
		while(Q.size()>1){
			int a=Q.top();Q.pop();
			int b=Q.top();Q.pop();//提取队列最小的两个 
			Q.push(a+b);
			ans += (a+b);
		}
		
		Q.pop();

		printf("%d %d %.1f\n",8*s.length(),ans,8.0*s.length()/ans);
	} 
	return 0;
}

解题思路：

解决对输入字符串进行熵编码相关的计算问题。通过统计字符串中不同字符的出现频率，利用哈夫曼树的思想（通过优先队列实现）构建编码方案，分别计算出字符串使用 8 比特 ASCII 编码的比特数和最优前缀无关变长编码（基于哈夫曼编码思想）的比特数，进而得出压缩比。

分析：

1.字符频率统计：对输入字符串进行排序后，通过遍历字符串比较相邻字符，统计每个字符的出现次数，将出现次数存储在优先队列中。这种方式可以方便后续构建哈夫曼树时，快速获取每个字符的频率信息。

2.哈夫曼树构建（利用优先队列）：哈夫曼树是一种用于实现最优前缀无关变长编码的树状结构，其核心思想是让出现频率高的字符使用更短的编码。代码中利用优先队列来模拟哈夫曼树的构建过程，优先队列中元素按从小到大的顺序排列（greater）。每次从优先队列中取出两个最小的频率值（代表两个节点），将它们合并为一个新的节点（频率为两者之和），并将新节点的频率值重新加入优先队列，重复此过程直到优先队列中只剩下一个元素，此时这个元素就是哈夫曼树的根节点的频率值。

3.编码长度计算：在构建哈夫曼树的过程中，每次合并两个节点时，将它们的频率之和累加到 Huff 变量中，最终 Huff 变量的值就代表了使用最优前缀无关变长编码时字符串所占用的比特数。对于只有一种字符的特殊情况，直接将字符出现次数作为编码长度。

步骤实现

1.输入处理：使用 getline(cin, s) 不断读取输入字符串，当读取到字符串为 "END" 时停止输入。

2.初始化与 ASCII 编码比特数计算：每次读取新字符串后，先清空优先队列，然后计算字符串使用 8 比特 ASCII 编码的比特数 Asc，即字符串长度乘以 8。

3.字符频率统计：对字符串进行排序，通过遍历比较相邻字符，统计每个字符的出现次数，并将出现次数依次加入优先队列。

4.哈夫曼编码比特数计算：

1.若优先队列中只有一个元素（即字符串中只有一种字符），直接将该元素的值赋给 Huff。

2.否则，不断从优先队列中取出两个最小的元素，将它们的和重新加入优先队列，并将这个和累加到 Huff 中，直到优先队列中只剩下一个元素，此时 Huff 即为使用最优前缀无关变长编码的比特数。

5.输出结果：计算压缩比（(double)Asc/Huff*1.0），按照格式输出 ASCII 编码的比特数、最优前缀无关变长编码的比特数和压缩比。

c++实现：

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  string s;
  priority_queue<int, vector<int>, greater<int> > q;
  while(getline(cin, s) && s != "END") {
      while(q.size()) q.pop();
      int Asc = s.length() * 8;
      sort(s.begin(), s.end());
      int t = 1;
      for(int i = 1; i < s.length(); i++) {
          if(s[i] != s[i-1]) {
              q.push(t); t = 1;
          }
          else t++;
      }
      q.push(t);
      int Huff = 0;
      if(q.size() == 1) Huff = t; // 只出现一种字符时特判
      while(q.size() > 1) {
          int a = q.top(); q.pop();
          int b = q.top(); q.pop();
          q.push(a+b);
          Huff += (a+b);
      }
      q.pop();
      printf("%d %d %.1f\n", Asc, Huff, (double)Asc/Huff*1.0);
  }
}