摘要
Title: 3531. 哈夫曼树
Tag: 哈夫曼树、小根堆
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

3531. 哈夫曼树

• 题意

  给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
  现在，给定 N 个叶子结点的信息，请你构造哈夫曼树，并输出该树的带权路径长度。
  相关知识：
  1、路径和路径长度
  在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L−1。
  2、结点的权及带权路径长度
  若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
  3、树的带权路径长度
  树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL。

• 思路

  注意给的是：N个叶子结点（而不是合成结点），其实也就相当于合并果子里的果子，一步一步挑最小的结点进行合成

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-08-07 20:13:36
  * @FilePath: \Acwing\3531\3531.cpp
  * @LastEditTime: 2022-08-07 21:36:05
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #define SZ(X) ((int)(X).size())
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(0);                                                                                                        \
      cout.tie(0)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  const int INF = INT_MAX;
  const int N = 1e6 + 10;
  
  signed main()
  {
      IOS;
      int n;
      cin >> n;
  
      priority_queue<int, vector<int>, greater<int>> q;
  
      for (int i = 1; i <= n; ++i)
      {
          int x;
          cin >> x;
          q.push(x);
      }
      int res = 0;
      while (SZ(q) > 1)
      {
          auto t1 = q.top();
          q.pop();
          auto t2 = q.top();
          q.pop();
  
          res += t1 + t2;
          q.push(t1 + t2);
      }
  
      cout << res << '\n';
      return 0;
  }