10. 计算WPL
发布时间
阅读量：
阅读量
Huffman编码是一种广泛应用在通信系统中的变长编码方法。其核心优势在于：通过优化字符编码比例，能够实现对信息进行最小化总码长的有效编码。
测试用例1：
输入：
5
7
5
2
4
9
输出：
WPL=60
测试用例2：
输入：
5
2
4
2
3
3
输出：
WPL=32
测试用例3：
输入：
1
15
输出：
0
解析：这道题目与上学期程设中的一道题《郭老师家的果园》有相似之处。以数值序列7、5、2、4、9为例，在初始状态下需要完成一系列的操作以达到最终目标。首先找出序列中的前两个最小值（即2和4），然后进行一次合并操作（将它们与相邻元素结合形成新的子序列）。接着，在新的序列中再次找出前两个最小值（即5和6），进行二次合并操作；随后，在新的序列中再次找出前两个最小值（即7和9）进行第三次合并操作……特别地，在整个过程中若只剩下单一数字，则无需任何操作；最终总耗能即为所有步骤中所累加的结果。
代码
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int last = 0, sum = 0, len;
void FindMin(int num[])
{
int x1 = last, x2 = last;
int min = num[last];//定义最小
int min2 = INT_MAX;//定义第二最小
for (int i = last; i <len; i++)
{
if (num[i]<min)
{
min = num[i];
x1 = i;
}
}//获得最小
for (int i = last; i < len; i++)
{
if (num[i] <= min2 && i != x1)
{
min2 = num[i];
x2 = i;
}
}//获得第二小
num[x2] = min + min2;
sum += num[x2];
if (x2 == last)
num[x1] = num[x2];
else
num[x1] = num[last];
num[last] = 0;
last++;
}
int main()
{
int n;
int num[10005] = { 0 };
scanf("%d", &n);
len = n;
if (len == 1)
{
printf("%d\n", num[0]);
return 0;
}
for (int i = 0; i < n; i++)
scanf("%d", &num[i]);
while (n > 1)
{
FindMin(num);
n--;
}
printf("WPL=%d\n", sum);
//system("pause");
return 0;
}全部评论 (0)
还没有任何评论哟~