算法导论——浅谈贪心

# 0.~~闲谈~~课前 ## 1.介绍 贪心，一种~~不可描述~~在**NOIP中较为常考的算法**，虽然比较好写，但是个人认为还是有一定介绍必要的 ## 2.引入 我们来考虑这样一个问题：**一堆人中要选出$k$个人，请问该如何选呢使得总钱数最多呢？** 你一定会说，**选钱最多的$k$个人呗**，没错，这就是简单的贪心 # 1.前置知识 - 有一定的数学思想 - ~~很贪心~~了解贪心思想 - 会简单的程序 # 2.例题 ## 1.排序 [看一下这道题目](https://www.luogu.org/problemnew/show/P1223)，看标签就知道，这是一道**简单的排序题**，那么，为什么要强调**排序**呢？因为**排序是贪心重要的思想之一** 为什么这么说呢？其实，在0.2中已经说过了，钱最多的人的选法自然是排序了，排序**能使贪心的正确性得到保证**，这也使得大部分贪心的时间复杂度是$O \left ( n\log n \right )$ ## 2.二分 二分分为二分查找和二分答案，贪心中二分答案较多，当然也有如[此题](https://www.luogu.org/problemnew/show/P1678)一样的二分查找 二分答案，是**贪心的进步**，它从$O \left ( n \right )$的暴力查找进化为$O \left ( \log n \right )$，这使得贪心的时间复杂度**再次降低** # 3.与其它算法的结合 看到这里，有人表示：**啊，贪心多简单啊！** 没错，麻烦接收一下[这份清单](https://www.luogu.org/problemnew/lists?name=&orderitem=difficulty&tag=7&content=0&type=&page=6)，走好不送，当然**新人们也不要过于害怕** 举个例子，[NOIP2017PJT4](https://www.luogu.org/problemnew/show/P3957)，这是一道**DP与二分答案的结合**，当然，这道题的难点是在于**DP+单调队列优化** # 4.与其他算法的转换 这种题目太多了，例如[这题](https://www.luogu.org/problemnew/show/P1208)，它是**背包与贪心的互换**，不过贪心更好写，也更好想，甚至**连时间复杂度都优于DP** 具体思想如下：**先按价格排序，尽量买更便宜的**，典型贪心 # 5.其他例题 例如**判断线段是否重合及所覆盖范围**，**求最优解**，**最大解最小/最小解最大**等等，使用范围~~奇广无比~~很广泛 ，很多地方都能用上 # 6.总结 贪心时间复杂度$O \left ( n\log n \right )$/$O \left ( n \right )$，空间复杂度不会增加多少，因此忽略不计 最后，如果还有不懂的，请参见： [我的二分](https://www.luogu.org/blog/70592/suan-fa-dao-lun-er-fen) [简单贪心](https://www.cnblogs.com/hezhihao/p/4038487.html)