重编码-K

重编码-K

背景

小粽学习了哈夫曼树之后，自己设计了贪心算法，用两个队列就过掉了《重编码》这道题。

小粽想：那堆的算法有什么用呢？为了解决小粽的疑惑，邓老师委托小莉命制了这道题目……

描述

有一篇文章，文章包含 nn 种单词，单词的编号从 11 至 nn，第 ii 种单词的出现次数为 wiwi。

现在，我们要用一个 kk 进制串（即只包含 0,1,...,k-10,1,...,k−1 的串） sisi 来替换

第 ii 种单词，使其满足如下要求：对于任意的 1≤i<j≤n1≤i<j≤n，都有 sisi 不是 sjsj 的前缀（这个要求是为了避免二义性）。

你的任务是对每个单词选择合适的 sjsj，使得替换后的文章总长度（定义为所有单词出现次数与替换它的 kk 进制串的长度乘积的总和）最小。求这个最小长度。

字符串 S1S1（不妨假设长度为 nn）被称为字符串 S2S2 的前缀，当且仅当：S2S2 的长度不小于 nn，且 S1S1 与 S2S2 前 nn 个字符组组成的字符串完全相同。

输入格式

第一行两个整数 nn 和 kk 。

第 2 行到第 n+1n+1 行，第 i+1i+1 行包含一个正整数 wiwi，表示第 ii 种单词的出现次数。

输格式

表示整篇文章重编码后的最短长度

输入样例 1

输样例 1

样例 2

点此下载。

限制

对于 100% 的数据，满

足 1≤n≤3×105,2≤k≤10,1≤wi≤1091≤n≤3×105,2≤k≤10,1≤wi≤109； 对于 40% 的数据，满足 n≤3000n≤3000；

对于 35% 的数据，满足 k=2k=2。

代码

#include <queue> #include <cstdio> #include <vector> #include<iostream>

#pragma warning(disable:4996) using namespace std;

typedef long long LL;

// =================== 代码实现开始 ========================

//Q:小根堆

/*Q作为小根堆，小根堆共有1+log(k)(n-1)(其中k为log的底数)层，为了用堆求Huffman树，故每次取出小根堆中前n个节点，以建立一个父节点

(注意新组成的父节点不能是任何一个单词的节点，但可以是其他单词节点的兄弟节点，这是为了避 免语义重复)

由小的节点组成堆底，并组成父节点与其他次小的节点合并再形成父节点，以此循环

*/

//assQ:辅助队列，为节约形成父节点后还需插入到小根堆中所需要的O(logn)时间priority_queue<LL, vector<LL>, greater<LL> > Q;

queue<LL> assQ;

// n: 初始点数

// k: 哈夫曼树的叉树

// w: w[i] 表示第i个点的点权

//返回值：最终编码的长度

LL solve(const vector<LL>& w, int n, int k)

{

// 在这里设计你的算法

for (int i = 0; i < n; i++)

{

Q.emplace(w[i]);

}

int r = ((k - 1) - ((n - 1) % (k - 1))) % (k - 1);//由于所给的不一定是满k叉树，当所给的条件不满足k叉树时，增加权值为0的节点

n += r;

while (r--)

assQ.push(0);//为形成满k叉树(百度百科中的国外的满k叉树的定义)

LL sum = 0;

while (n != 1)//当n=1时，说明总长度合并完成

{

LL tmpf=0;//临时的父节点，组成新的父节点后压入assQ中以节约时间

for (int i = 0; i < k; i++)

{

if (Q.empty()||!assQ.empty() && assQ.front() < Q.top())//若assQ中的节点较小，说明应当先从assQ中取出节点来合并

                                                   //若Q为空，说明节点全在assQ中(例如全部节点的权值都一样的情况)

{

tmpf += assQ.front();

assQ.pop();

continue;

}

tmpf += Q.top();

Q.pop();

}

sum += tmpf;

assQ.push(tmpf);//将新产生的父节点压入assQ中

n -= k - 1;

}

return sum;

}

// ================== 代码实现结束 ======================

int main()

{

int n, k;

scanf("%d%d", &n, &k);

vector<LL> w;

w.reserve(n);

for (int i = 0; i < n; i++) {

LL a;

scanf("%lld", &a);

w.push_back(a);

}

printf("%lld\n", solve(w, n, k));

return 0;

}