题解 | #哈夫曼树#
哈夫曼树
https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;cin>>n;
vector<int>v;
while(n--){
int temp;cin>>temp;
v.push_back(temp);
}
sort(v.begin(),v.end());
int totalWeight = 0;
int sum=0;
while(v.size()!=1){
totalWeight=v[0]+v[1];
sum+=totalWeight;
v.erase(v.begin()+1);
v.erase(v.begin());
v.push_back(totalWeight);
sort(v.begin(),v.end());
}
cout<<sum<<endl;
}
// 64 位输出请用 printf("%lld")
容易想到，但是复杂度很高
查看10道真题和解析