题解 | 合并果子-NOIP2004提高组复赛
合并果子
https://ac.nowcoder.com/acm/contest/252/B
算法知识点: 贪心,哈夫曼树,堆,优先队列
复杂度： )
解题思路：
经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。
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;
} 
OPPO公司福利 1103人发布