文章目录
前言
一、贪心
二、AcWing 148. 合并果子
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：贪心——Huffman树，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、贪心
贪心：利益最大化，即找到最优的情况，贪心问题难在证明，即你可能能推断出这个题目的正确解法，但是这个解法下为什么就是最优解不好证明。
二、AcWing 148. 合并果子
本题链接：AcWing 148. 合并果子
本博客给出本题截图
本题分析
本题用到了小根堆，即优先队列，优先队列（STL）见博客：（先鸽），手写堆见博客：（先鸽）
我们优先队列维护所有的果子，每次把堆顶的两个元素弹出相加，然后把结果载加入到堆中，最后直到堆中只有一个元素的时候就是结束的标志
AC代码
#include <cstdio> #include <algorithm> #include <queue> using namespace std; int main() { int n; scanf("%d", &n); priority_queue<int, vector<int>, greater<int>> heap; for (int i = 0; i < n; i ++ ) { 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", res); return 0; }
三、时间复杂度
关于贪心——Huffman树的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
