重编码发表时间：2022-10-27 20:15 重编码 问题描述 有一篇文章，文章包含 nn 种单词，单词的编号从 11 至 nn，第 i 种单词的出现次数为 wiwi。 现在，我们要用一个 2 进制串（即只包含 0 或 1 的串） sisi 来替换第 i 种单词，使其满足如下要求：对于任意的 1≤i,j≤n,i≠j1≤i,j≤n,i≠j，都有 sisi 不是 sjsj 的前缀。（这个要求是为了避免二义性） 你的任务是对每个单词选择合适的 sisi，使得替换后的文章总长度（定义为所有单词出现次数与替换它的二进制串的长度乘积的总和）最小。求这个最小长度。 字符串 S1S1（不妨假设长度为 nn）被称为字符串 S2S2 的前缀，当且仅当：S2S2 的长度不小于 nn，且 S1S1 与 S2S2 前 nn 个字符组组成的字符串完全相同。 输入格式 第一行一个整数 nn，表示单词种数。 第 2 行到第 n+1n+1 行，第 i+1i+1 行包含一个正整数 wiwi，表示第 ii 种单词的出现次数。 输格式 输出一行一个整数，表示整篇文章重编码后的最短长度。 样例输入 样例输 样例解释 一种最优方案是令 s1s1=000，s2s2=001，s3s3=01，s4s4=1。这样文章总长即为 1*3+1*3+2*2+1*2=12。 另一种最优方案是令 s1s1=00，s2s2=01，s3s3=10，s4s4=11。这样文章总长也为 12。 数据范围 对于第 1 个测试点，保证 n=3n=3。对于第 2 个测试点，保证 n=5n=5。 对于第 3 个测试点，保证 n=16n=16，且所有 wiwi 都相等。对于第 4 个测试点，保证 n=1000n=1000。 对于第 5 个测试点，保证所有 wiwi 都相等。 对于所有的 7 个测试点，保证 2≤n≤1062≤n≤106，wi≤1011wi≤1011。时间限制：2 sec 空间限制：256 MB 提示 [我们希望越长的串出现次数越少，那么贪心地考虑，让出现次数少的串更长。] [于是我们先区分出出现次数最少的 2 个串，在它们的开头分别添加 0 和 1。] [接着，由于它们已经被区分（想一想，为什么？），所以我们可以把它们看作是**一个** 单词，且其出现次数为它们的和，然后继续上面的“添数”和“合并”操作。] [这样，我们不停地“合并单词”，直到只剩 1 个单词，即可结束。] [可以证明这是最优的。] [朴素的实现是 O(n2)O(n2) 的，可以用二叉堆或 std::priority_queue 将其优化至 O(nlogn)O(nlogn)。] 代码 #include<iostream> #include<queue>
using namespace std;
int main() { int n; cin >> n; priority_queue <long long, vector<long long>, greater<long long>> pq; /*类似于二叉堆实现的队列，较小值的元素排在前面(可自定义升序或者降序及比较的方式),由于是利用堆实现的比较，故最大比较次数为O(nlogn) 类似于huffman树，通过将最小的两个子节点之和获得父节点，并将该父节点放到 priority_queue合适的位置 将新的父节点放到合适位置之后，再求和，通过此来获得每个子节点应当放在类Huffman树的二 叉树的第几层(每相加一次相当于将该单词下移一层) 从而获得该单词应当由几个0或1构成(可以想象成父节点左边的子节点前面加一个0，右边加一个1) */
long long* w=new long long[n];//某单词出现的次数w[i] for (int i = 0; i < n; i++) { cin >> w[i]; }
bool allSame = true;//比较是否所有的w[i]都一样，若都一样则不使用priority_queue，以免浪费比较时间 for (int i = 1; i < n; i++) { if (w[i] != w[i - 1]) { allSame = false; break; } }
long long len = 0;//Huffman编码的所有单词的总长
if (!allSame)//当不是所有单词出现次数w[i]都一样时，插入二叉堆中 { for (int i = 0; i < n; i++) { pq.emplace(w[i]); } } else//若w[i]都一样，则直接使用普通队列，省去priority_queue的比较过程 { queue<long long> p; long long temp = 0;//用于存储合并元素后的值 for (int i = 0; i < n; i++) { p.emplace(w[i]); } while (p.size() != 1)//当队列中还存在有两个以上的单词时，说明该类huffman树内节点距离求和未完成，需要继续进行 { for (int i = 0; i < 2; i++)//由两个较小的子节点的值相加(w[i]+w[i+1])获得该父节点的值，并将该父节点放到队列的末尾(由于w[i]都一样，故相加后的值必为整个队列的最大 值) { temp += p.front(); p.pop(); } p.emplace(temp); len += temp; temp = 0; } cout << len << endl; return 0; }
long long temp = 0;//用于存储合并元素后的值 for(int i = 0; i < n; i++) { while (pq.size() != 1) { for (int i = 0; i < 2; i++)//求父节点之和，并将新的父节点插入到二叉树合适 的层数之中 { temp += pq.top(); pq.pop(); } pq.emplace(temp); len += temp; temp = 0; } } cout << len << endl; return 0; } |