UVA12676 Inverting Huffman

简介: UVA12676 Inverting Huffman

UVA12676 Inverting Huffman


题目描述:

静态哈夫曼编码是一种主要用于文本压缩的编码算法。给定一个由 N 个不同字符组成的特定长度的文本,算法选择 N 个编码,每个不同的字符一个编码。使用这些编码压缩文本,当选择编码算法构建一个具有 N 个叶子的二叉树时,对于 N≥2,树的构建如下:


对文本中的每个不同字符,构建一个仅包含单个结点的树,并为其分配权值,权值与文本中该字符出现的次数一致。

构建一个包含上述 N 棵树的集合 s。

当 s 包含多于一棵树时:

(a) 选择最小的权值 t1∈s,并将其从 s 中删除;

(b) 选择最小的权值 t2∈s,并将其从 s 中删除;

(c) 构建一棵新树 t,t1 为其左子树,t2 为其右子树,并且 t 的权值为 t1、t2 权

值之和;

(d) 将 t 加入 s 集合。

返回保留在 s 中的唯一一棵树。

对于文本““abracadabra”,由上述过程生成的树,可以像下图左侧,其中每个内部结点编辑有子树根的权值。请注意获得的树也可以像下图右侧或其它,因为在步骤 3(a)、3(b)中,结合可能包含几个权值最小的树。

20210221130906747.jpg

对文本中的每个不同字符,其编码取决于最终树中从根到对应字符的叶子之间的路径,编码的长度是这条路径中的边数(与路径中的内部结点一致)。假设该算法构建的是左侧的树,“r”的代码长度为 3,“d”的代码长度为 4。

根据算法选择的 N 个代码的长度,找所有字符总数的最小值。

输入:

输入文件包含多个测试用例,每个测试用例如下所述:

第一行包含一个整数 N(2≤N≤50),表示文本中出现的不同字符数。

第二行包含 N 个整数 Li(1≤Li≤50,i=1,2,…,N),表示由 huffman 算法生成的不同字符的编码长度。

假设至少存在一棵上述算法构建的树,可以生成具有给定长度的编码。


输出:

对每个测试用例,输出一行,表示所有字符总数的最小值。


样例输入

2

1 1

4

2 2 2 2

10

8 2 4 7 5 1 6 9 3 9


样例输出

2

4

89


题解:

根据编码长度,推测最小字符数。

举例:

4

3 1 2 3

最长编码为 3,即最大深度为 3。

20210221131020376.jpg


算法设计:

(1) 每一层用一个深度数组 deep[]记录该层结点权值,该层每个结点的权值初始化

为 0,等待推测权值;

(2) 根据输入的编码长度算出最大长度即最大深度 maxd。

(3) 从最大深度 maxd 向上计算并推测,直到树根。开始时 temp=1;

⚫ i=maxd:第 i 层的结点权值如果为 0,则初始化为 temp(此时,temp=1)。

对第 i 层从小到大排序,然后将第 i 层每两个合并,权值放入上一层(i-1

层)。更新 temp 为第 i 层排序后的最后一个元素(最大元素)。

⚫ i=maxd-1:重复上述操作;

⚫ i=0:结束。输出第 0 层第一个元素。


解题思路

本题主要考察哈夫曼树的应用;

题目要求给出每个字符出现的长度,计算编码的最小长度.可以从后往前推,但要明白上一层的叶子结点值必须>=本层节点的最大值.最后一层值为1.然后依次往上推即可.最后根节点对应的权值便是编码的最小长度.


代码实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXSIZE = 60;
vector<long long> deep[MAXSIZE];
int n,x,maxd;
long long temp = 1;
int main()
{
  while (cin >> n)
  {
    for (int i = 0; i < n; i++)
    {
      cin >> x;
      deep[x].push_back(0);
      maxd = max(maxd, x);//求最大深度
    }
    for (int i = maxd; i > 0; i--)//从maxd向上推测
    {
      for (int j = 0; j < deep[i].size(); j++)//第i层初始化
      {
        if (!deep[i][j])
        {
          deep[i][j] = temp;
        }
      }
      sort(deep[i].begin(), deep[i].end());//排序
      for (int j = 0; j < deep[i].size(); j += 2)//两两合并
      {
        deep[i - 1].push_back(deep[i][j] + deep[i][j + 1]);//新生成的节点放到上一层
      }
      temp = *(deep[i].end() - 1);//更新temp  上一层叶子结点权值 >= 该层的最大值.
    }
    cout << *deep[0].begin() << endl;//输出最小长度.
    //更新数据
    for (int i = 0; i < MAXSIZE; i++)//数组初始化
    {
      deep[i].clear();
    }
    maxd = 0;
    temp = 1;
  }
  return 0;
}
相关文章
|
人工智能 PyTorch 算法框架/工具
AI 容器镜像部署 Stable Diffusion
本文将基于阿里云 AMD 服务器和龙蜥 AI 容器服务,快速搭建出个人版文生图服务
|
6月前
|
人工智能 监控 安全
Gemini API 生产限流治理:从单点调用到企业网关
企业接入 Gemini API,技术难点不是发出请求,而是把模型调用变成可治理的基础设施。网关、限流、审计、成本和供应弹性做好之后,AI 能力才适合长期运行。
362 0
|
监控 网络协议 Linux
Linux网卡调优:RPS (Receive Packet Steering)
Linux网卡调优:RPS (Receive Packet Steering)
1185 0
|
9月前
|
BI
春节复工后,2026年1688店铺想突围,这份操作运营指南请收好!
春节后1688运营必做清单:分三阶段——急救重启(发货清零、视觉焕新)、赛道布局(定位选品、数据诊断)、流量抢跑(搜索优化、老客召回)。聚焦金冠培育、新品破零、层级提升,踩准平台节奏,抢占开年红利!
|
6月前
|
边缘计算 安全 定位技术
AIWCLOUD:免备案高防CDN、不限内容、抗投诉、在跨境金融级数据同步场景下
本文介绍一种专为跨境金融设计的免备案CDN架构,通过物理路径固化、PTP亚微秒时钟同步与MACsec链路层加密,实现低抖动、高安全、强合规的“数据专线级”传输,满足支付清算、外汇交易等场景的严苛要求。(239字)
348 8
|
5月前
|
机器学习/深度学习 Ubuntu 机器人
基于 Isaac Lab 的 Unitree Go2 四足机器人RL控制项目
基于 NVIDIA Isaac Lab 的 Unitree Go2 四足机器人强化学习工程已整理开源。项目包含 Task1 平地速度跟踪、Task2 多地形运动、Task3 自主导航避障、Task4 Sim2Real / RMA 抗扰训练,统一使用 skrl PPO,并提供 Ubuntu / Windows 脚本、world/env 测试、smoke training、日志与 checkpoint 管理。适合参考 Isaac Lab 四足机器人训练流程。具体内容请参考github链接进行阅读。
|
Web App开发 人工智能 JSON
深度测评:DeepSeek 对话导出工具 Top 3,公式不乱码、排版零折损的终极方案
本文为AI技术博主推荐三款高效导出DeepSeek对话的工具:专为iOS/macOS设计的App,支持多格式且完美保留代码高亮与公式;,适用于Chrome等主流浏览器;以及内置在QQ浏览器中的导出功能,无需额外安装,适合日常快速存档。结合官方导出方式与使用建议,帮助用户根据设备与需求选择最佳方案,同时提醒注意数据隐私与兼容性问题。
2752 0
深度测评:DeepSeek 对话导出工具 Top 3,公式不乱码、排版零折损的终极方案
|
10月前
|
弹性计算 编解码 缓存
2026大放价,阿里云服务器经济型e、通用算力型u2a、计算型c9i等实例最新收费标准与活动价格
2026年阿里云活动提供了经济型e、通用算力型u1和u2a、计算型c9i、通用型g9i、内存型r9i等多款云服务器ECS实例规格,价格从99元/年起,满足不同用户和业务场景需求。活动包括按量和按月收费标准,及包1至5年收费详情,用户可享优惠价格。此外,阿里云提供丰富优惠券和补贴,如学生无门槛券、企业出海和迁云补贴,个人用户新客户专享满减券等,进一步降低成本,助力用户普惠上云,实现高性能与稳定性的云服务器体验。
822 2
|
机器学习/深度学习 人工智能 算法
VE-Bench:北京大学开源首个针对视频编辑质量的评估指标,从多角度考虑审美并准确地评估视频编辑效果
北京大学开源了首个针对视频编辑质量评估的新指标 VE-Bench,旨在通过人类感知一致的度量标准,更准确地评估视频编辑效果。
1352 14
VE-Bench:北京大学开源首个针对视频编辑质量的评估指标,从多角度考虑审美并准确地评估视频编辑效果
|
算法 程序员
程序设计的五个步骤
程序的设计过程,并不是立刻就进行代码设计,一般来讲包括设置文件的存放位置、说明书的设计、代码设计、程序测试、程序调试、注释说明。
1823 6