算法知识点: 贪心,哈夫曼树,堆,优先队列
复杂度:
解题思路:
经典哈夫曼树的模型,每次合并重量最小的两堆果子即可。
C++ 代码:
#include <iostream> #include <algorithm> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); priority_queue<int, vector<int>, greater < int>> heap; while (n--) { int x; scanf("%d", &x); heap.push(x); } int res = 0; while (heap.size() > 1) { int a = heap.top(); heap.pop(); int b = heap.top(); heap.pop(); res += a + b; heap.push(a + b); } printf("%d\n", res); return 0; }