问题描述
有一篇文章，文章包含 n 种单词，单词的编号从 1 至 n，第 i 种单词的出现次数为 w[i]。
现在，我们要用一个 2 进制串（即只包含 0 或 1 的串） s[i] 来替换第 i 种单词，使其满足如下要求：对于任意的 1≤i,j≤n（i≤j），都有 s[i] 不是 s[j] 的前缀。（这个要求是为了避免二义性）
你的任务是对每个单词选择合适的 s[i]，使得替换后的文章总长度（定义为所有单词出现次数与替换它的二进制串的长度乘积的总和）最小。求这个最小长度。
字符串 S1（不妨假设长度为 n）被称为字符串 S2 的前缀，当且仅当：S2 的长度不小于 n，且 S1 与 S2 前 n 个字符组组成的字符串完全相同。
输入格
第一行一个整数 n，表示单词种数。
第 2 行到第 n+1 行，第 i+1 行包含一个正整数 w[i]，表示第 i 种单词的出现次数。
输出格式
输出一行一个整数，表示整篇文章重编码后的最短长度。
样例输入
41122
样例输出
12
样例解释
一种最优方案是令 s[1]=000，s[2]=001，s[3]=01，s[4]=1。这样文章总长即为 1*3+1*3+2*2+1*2=12。
另一种最优方案是令 s[1]=00，s[2]=01，s[3]=10，s[4]=11。这样文章总长也为 12。
提示
[我们希望越长的串出现次数越少，那么贪心地考虑，让出现次数少的串更长。]
[于是我们先区分出出现次数最少的 2 个串，在它们的开头分别添加 0 和 1。]
[接着，由于它们已经被区分（想一想，为什么？），所以我们可以把它们看作是**一个**单词，且其出现次数为它们的和，然后继续上面的“添数”和“合并”操作。]
[这样，我们不停地“合并单词”，直到只剩 1 个单词，即可结束。]
[可以证明这是最优的。]
[朴素的实现是 O(n^2) 的，可以用二叉堆或__std::priority_queue__将其优化至 O(nlogn)。]
一. 图解
可使用优先队列的小顶堆去实现
二. 具体实现（C++版）
#include <bits/stdc++.h>
using namespace std;
// ================= 代码实现开始 =================
typedef long long ll;
//pq：一个小顶堆优先队列，用于辅助后续计算
priority_queue<ll,vector<ll>,greater<ll> > pq;
// 这是求解整个问题的函数
// w：题目描述中的 w（所有）
// n：题目描述中的 n
// 返回值：答案
long long getAnswer(int n, vector<long long> w) {
//将所有w加入优先队列pq中
for(int i=0; i<n; ++i)
pq.push(w[i]);
ll sum = 0;//置零返回值
while(pq.size()> 1){//当pq中仍有超过多少元素时进行循环呢？
ll newEle = 0;//这是本次合并后将要加入队列的新元素
//从pq中取出最小的两个元素并合并
for(int k = 0; k<2; ++k){
newEle += pq.top();
pq.pop();//不能漏
}
sum += newEle;//将本次合并对答案的贡献加入答案
pq.push(newEle);//将新元素加入队列
}
return sum;//返回答案
}
// ================= 代码实现结束 =================
三. 补充C++的priority_queue用法（大顶堆，小顶堆）
1、优先输出大数据
priority_queue<Type, Container, Functional>
Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。
如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
例：
#include<iostream>
#include<queue>
using namespace std;
int main(){
priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
for(int i=0;i<3;i++){
cout<<pq.top()<<l;
pq.pop();
}
return 0;
}
输出：3 2 1
2、优先输出小数据
priority_queue<ll,vector<11>,greater<ll>> pq;
例：
#include<iostream>
#include<queue>
using namespace std;
int main(){
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(1);
pq.push(2);
pq.push(3);
for(int i=0;i<3;i++){
cout<<p.top()<<l;
p.pop();
}
return 0;
}
输出：1 2 3
