重编码

/*重编码
问题描述
有一篇文章，文章包含 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 种单词的出现次数。

输出格式
输出一行一个整数，表示整篇文章重编码后的最短长度。

样例输入
4
1
1
2
2
样例输出
12*/
-----------------------------------------------------------------------------------------------------------------

#include <bits/stdC++.h>
using namespace std;

typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > pq;//优先队列 --- 自小到大排序
// priority_queue<ll> pq;//自大到小排序

/*通过哈夫曼树的性质来 求编码长度*/
long long Haffman(int n,vector<ll> w){
    /*将vector w内的数值 放入 优先队列（实际是排序功能）*/
    for(int i = 0;i < n;i++){
        pq.push(w[i]);
    }
    ll sum = 0;//sum来统计 编码的最大长度
    //当pd.size() = 1 时 只剩一个根节点
    while (pq.size() > 1) {
      ll temp = 0;
      //将最小的两个 节点相加 生成父节点
      for(int i = 0;i < 2;i++){
        temp += pq.top();//区最小的节点
        pq.pop();
      }
      sum += temp;
      pq.push(temp);//生成新节点
    }
    return sum;
}
int main(int argc, char const *argv[]) {
  int N;
  scanf("%d",&N);
  vector<ll> w;

  for(int i = 0;i < N;i++){
    int v;
    scanf("%d",&v);
    w.push_back(v);
  }

  printf("%lld",Haffman(N,w));
  return 0;
}