题目描述
分析
霍夫曼编码的应用。
本题没有必要构造一棵完整的霍夫曼树。只需利用霍夫曼编码的原理，每次挑选频率最低的两个元素进行合并。（显然，可以利用优先级队列，这里用数组来模拟）
源码
//每次挑出现频率最小的两个元素，应该用优先级队列！！！！！！！！！！#include#include #include int unionFre(int fre[26]);int main(){ int frequency[26]; //记录每个字母出现的频率 int n; int m; char input[10000]; int letterNum; //出现的小写字母的个数 int len; int result; int i, j; scanf("%d", &n); while (n --) { scanf("%d", &m); scanf("%s", &input); //初始化 memset(frequency, 0, sizeof(frequency)); //统计每个字母出现的次数 len = strlen(input); for (i = 0; i < len; i ++) { frequency[input[i]-'a'] ++; } //没出现的字母频率均设为最大值 letterNum = 26; for (i = 0; i < 26; i ++) { if (frequency[i] == 0) { letterNum --; frequency[i] = INT_MAX; } } //如果字符串只由一个字母组成 if (letterNum == 1) { result = frequency[input[0]-97]; if (result <= m) printf("yes\n"); else printf("no\n"); continue; } //循环(letterNum-1)次，每次挑选出现频率最低的两个元素进行合并 //并更新result值，加上被合并的两个元素的频率和 result = 0; for (i = 0; i < letterNum-1; i ++) { result = result + unionFre(frequency); } if (result <= m) printf("yes\n"); else printf("no\n"); } return 0;}//合并函数int unionFre(int fre[26]){ int min, secondMin; int minIndex, secondMinIndex; int temp; int i; min = fre[0]; minIndex = 0; secondMin = fre[1]; secondMinIndex = 1; if (min > secondMin) { temp = min; min = secondMin; secondMin = temp; temp = minIndex; minIndex = secondMinIndex; secondMinIndex = temp; } //找出频率最低的两个元素 for (i = 2; i < 26; i ++) { if (fre[i] < min) { secondMin = min; secondMinIndex = minIndex; min = fre[i]; minIndex = i; } else if (fre[i] < secondMin) { secondMin = fre[i]; secondMinIndex = i; } } //合并两个元素 fre[minIndex] = min + secondMin; fre[secondMinIndex] = INT_MAX; return (min + secondMin);}