目录

1. 贪心问题概述
2. 区间问题
3. Huffman树
4. 排序不等式
5. 绝对值不等式
6. 推公式

1. 贪心问题概述

贪心算法，思路是每次都选取局部最优解但局部最优解不一定是全局最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解

常用的证明思路

贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明

反证法：
如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。

归纳法：
先算得出边界情况$($例如$n$ $=$ $1)$的最优解$F(1)$，然后再证明：对于每个$n$，$F(n + 1)$都可以由$F(n)$推导出结果

一般的贪心做法

按某种条件排序一下，然后猜下怎么做，试着大概证明下，验证几个例子，然后就做、

2. 区间贪心

区间贪心，一般就是按左端点或者右端点拍下序，然后猜性质，就做的。有些记模型的味道在里面，拿经验做题

AcWing 905. 区间选点 https://www.acwing.com/solution/content/80992/
AcWing 908. 最大不相交区间数量 https://www.acwing.com/solution/content/81010/
AcWing 906. 区间分组 https://www.acwing.com/solution/content/81023/
AcWing 907. 区间覆盖 https://www.acwing.com/solution/content/81102/

3. Huffman树

这个算是一个数据结构知识点了

哈夫曼树是树的带全路径长度最短的树，构造方法如下

霍夫曼算法用于构造一棵霍夫曼树，算法步骤如下：

初始化： 由给定的$n$个权值构造$n$棵只有一个根节点的二叉树，得到一个二叉树集合$F$

选取与合并： 从二叉树集合$F$中选取根节点权值最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和

删除与加入： 从$F$中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到$F$中
重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树

AcWing 148. 合并果子 https://www.acwing.com/solution/content/81088/

4. 剩余习题

剩下的题，我感觉主要还是背模型，很难总结出规律一类的

AcWing 913. 排队打水 https://www.acwing.com/solution/content/81475/
AcWing 104. 货仓选址 https://www.acwing.com/solution/content/81479/
AcWing 125. 耍杂技的牛 https://www.acwing.com/solution/content/81486/