AcWing 149. 荷马史诗(二叉堆、小根堆、Huffman树、C++)

2023-10-20 05:50

本文主要是介绍AcWing 149. 荷马史诗(二叉堆、小根堆、Huffman树、C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • AcWing 149. 荷马史诗
  • 题目描述
  • 输入输出
      • 数据范围
      • 输入样例
      • 输出样例
  • 思路
  • C++实现

AcWing 149. 荷马史诗

题目地址:https://www.acwing.com/problem/content/151/

题目描述

一部《荷马史诗》中有 n 种不同的单词,从 1 到 n 进行编号。其中第 i 种单词出现的总次数为 wi 。

达达想要用 k 进制串 si 来替换第 i 种单词,使得其满足如下要求:

对于任意的 1 ≤ i,j ≤ n ,i ≠ j,都有:si 不是 sj 的前缀。

现在达达想要知道,如何选择 si,才能使替换以后得到的新的《荷马史诗》长度最小。

在确保总长度最小的情况下,达达还想知道最长的 si 的最短长度是多少?

一个字符串被称为 k 进制字符串,当且仅当它的每个字符是 0 到 k−1 之间(包括 0 和 k−1)的整数。

字符串 Str1 被称为字符串 Str2 的前缀,当且仅当:存在 1 ≤ t ≤ m,使得 Str1 = Str2 [1…t] 。

其中,m 是字符串 Str2 的长度,Str2[1…t] 表示 Str2 的前 t 个字符组成的字符串。

输入输出

第一行输入n、k,分别表示有 n 种单词,需要使用k进制字符串进行替换。
第2 - (n + 1) 行每行输入一个非负整数 wi ,表示第 i 种单词出现的次数。

数据范围

2 ≤ n ≤ 100000,
2 ≤ k ≤ 9
1 ≤ wi ≤ 10^12

输入样例

4 2
1
1
2
2

输出样例

12
2

思路

本题所构造的编码方式其实就是 Huffman 编码,我们把单词的出现次数 w1 ~ wn 作为 Huffman 树
叶子节点的权值,然后求出k 叉 Huffman 树。对于 Huffman 树的每个节点的k个分支,分别在边上标
记字符0 ~ k - 1.

此时,可以把这棵Huffman树看作一棵Trie树,就得到了使总长度最小的编码方式——单词 i 的编码就是从根节点到叶子节点 i 的路径上各条边的字符相连。一个单词不是另一个的前缀,其实就对应着: 在Trie树中,所有单词编码的末尾都在叶子节点上,而不在Trie树的一个内部节点上,恰好满足了这个性质。

同时,本题还要求最长的 si 长度最短,我们只需要在求Huffman 树时,对于权值相同的节点,优先考虑当前深度最小(已合并次数最小)的进行合并即可。

哈夫曼树,就是满足权值路径长度最短的树,因此我们这道题目直接可以开哈夫曼树处理即可。

在代码实现过程中,我们先将所有的值压入堆中,每个值的first存的是叶子节点的权值,即单词的出现次数,second存深度。然后,我们在执行上述贪心算法之前,补加一些额外的权值为0的叶子节点,使叶子节点的个数n满足 ( n - 1 ) mod ( k - 1 ) = 0。也就是说,我们让子节点不足k个的情况发生在最底层,而不是根节点处。在满足 ( n - 1 ) mod ( k - 1 ) = 0 时,执行“每次从堆中取出最小的k个权值的贪心算法就是正确的。

Trie树

C++实现

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
#define ll long long
#define endl '\n'typedef pair<ll, ll> pir;	//first存的是叶子节点的权值,即单词的出现次数,second存深度
const int mod = 0x7f7f7f7f;
const int N = 100010;ll a[N], min_len;
priority_queue<pir, vector<pir>, greater<pir> > heap;int main(void){IOSint n, k; cin >> n >> k;for(int i = 1; i <= n; i ++ ){ll x; cin >> x;heap.push({x, 0});}while((heap.size() - 1) % (k - 1) != 0){	//补全额外的叶子节点heap.push({0, 0});}while(heap.size() >= k){ll num = 0, deep = -1;for(int i = 1; i <= k; i ++ ){	//每次取出k个最小权值pir p = heap.top();heap.pop();num += p.first;deep = max(deep, p.second);}min_len += num;	//总权值heap.push({num, deep + 1});	//深度 +1}cout << min_len << endl << heap.top().second << endl;	//堆顶的数即为最长字符串的最短长度return 0;
}

这篇关于AcWing 149. 荷马史诗(二叉堆、小根堆、Huffman树、C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/245107

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(