考察知识点:贪心、优先队列、哈夫曼树
题目翻译一下就是 个节点构成一棵二叉树,求这棵树的最小带权路径长度。
哈夫曼树 是带权路径长度最小的树,所以本题只需要构造一棵哈夫曼树即可。
时间复杂度:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
void solve()
{
int n;
cin >> n;
priority_queue<int, vi, greater<int>> pq;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
pq.push(a);
}
int ans = 0;
while (pq.size() > 1)
{
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
ans += a + b;
pq.push(a + b);
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}