【普及】贪心算法专项训练

## Update Log - 2021.4.14 更新了一顿下面的题解。 - 2021.7.21 加了一批反悔贪心的题目。 ## 贪心原理 贪心算法的核心就是一个字：贪。总是做出当前看来最优的选择，因此可知，贪心算法不从整体去考虑，它做出的选择也是局部最优选择，从而达到全局优化选择。我们只关注目前的利益，从而达到利益最大化，尽管贪心算法不一定能得到最优解，面对相当数量的一部分问题，我们是可以得到正确的答案的。 从问题的某一个初始解，一步步推论，保证每一步都是最为优化的，出发逐步逼近给定的目标，以尽可能快的地求得更好的解。 当接下来的任意一步都无法达到最优时，贪心算法结束。 ## 贪心算法的弊病 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 下面给出一些例题。 **电池的寿命** 有很多电池，使用寿命有所不同，需要两个电池。譬如有的能使用 $5$ 个小时，有的可能就只能使用 $3$ 个小时，此时只能用 $3$ 个小时，有一个电池剩下的电量无法使用，因为我们需要 $2$ 枚电池同时使用。现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。 那么我们来分析一下两种情况。 - 如果有一枚电池，电量比任何其他的电池之和都要大，很容易得到把其他电池用完就是最优解了。 - 如果不存在这枚电池，性感理解一下，就是把最大的电池拿出来，将其他的电池一点一点消耗到和这枚电池一样，然后全部用掉。 综上所述： - 若存在大于总电量一半的电池，输出其余电池的总电量。 - 反之输出全部的电量。 这样只需要 $O(n)$ 的输入后就可以得出答案，仅需判断并求和即可，没有难度 **[【深基12.例1】部分背包问题](https://www.luogu.com.cn/problem/P2240)** 这道题也是一个很简单的贪心。其实此题所谓的背包问题，看似需要使用动态规划，但是，**所有金币都可以随意分割**，那么显而易见的方法是： - 性价比排列，从最高性价比一直往下拿，拿到拿不动或者拿光了为止，是不是很简单？ - 核心思想：能拿就全拿，拿不下能拿多少拿多少，贵的先拿。 **货币使用问题** 尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。 **区间调度问题** 工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。 ## Dijkstra & Prim 迪杰斯特拉算法也是基于贪心的一种算法，其基本原理： 1. 循环找到当前离当前节点**最近**的节点（贪心）。 注：可以用堆或者优先队列进行优化。 2. 向下走，如果比之前标记过的最短路更短，就将这个节点进行标记（松弛）。 3. 将整个图走一遍，无优化时间复杂度 $O(n^2)$。 4. 每次都找最优，所以有局限，不能应对有负边的图。 ## 题目选择 训练贪心算法，可以从以下的几个方面： - 尝试着证明一道题贪心的正确性。 - 对于一道动规题目尝试举出贪心的反例。 - 尝试优化贪心，反悔贪心。 本次的题库依然按照难度排序，面向普及，按难度排序，适合由浅入深的同学，难度不超过紫，也会有橙题等适合入门的题目，可以循序渐进。 ## 纯粹贪心题目 - [P1007 独木桥](https://www.luogu.com.cn/problem/P1007) - [P1031 [NOIP2002 提高组] 均分纸牌](https://www.luogu.com.cn/problem/P1031) - [P2695 骑士的工作](https://www.luogu.com.cn/problem/P2695) - [P5639 【CSGRound2】守序者的尊严](https://www.luogu.com.cn/problem/P5639) - [P1056 [NOIP2008 普及组] 排座椅](https://www.luogu.com.cn/problem/P1056) - [P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G](https://www.luogu.com.cn/problem/P1090) - [P1106 删数问题](https://www.luogu.com.cn/problem/P1106) - [P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779) - [P2240 【深基12.例1】部分背包问题](https://www.luogu.com.cn/problem/P2240) - [P2630 图像变换](https://www.luogu.com.cn/problem/P2630) - [P3915 树的分解](https://www.luogu.com.cn/problem/P3915) - [P5514 [MtOI2019]永夜的报应](https://www.luogu.com.cn/problem/P5514) - [P1766 液体滴落](https://www.luogu.com.cn/problem/P1766) - [P2431 正妹吃月饼](https://www.luogu.com.cn/problem/P2431) - [P3619 魔法](https://www.luogu.com.cn/problem/P3619) - [P6155 修改](https://www.luogu.com.cn/problem/P6155) - [P1269 信号放大器](https://www.luogu.com.cn/problem/P1269) - [P1528 切蛋糕](https://www.luogu.com.cn/problem/P1528) - [P2127 序列排序](https://www.luogu.com.cn/problem/P2127) - [P2668 [NOIP2015 提高组] 斗地主](https://www.luogu.com.cn/problem/P2668) - [P1686 挑战](https://www.luogu.com.cn/problem/P1686) - [P2675 《瞿葩的数字游戏》T3-三角圣地](https://www.luogu.com.cn/problem/P2675) - [P3615 如厕计划](https://www.luogu.com.cn/problem/P3615) ## 反悔贪心题目 - [P1792 [国家集训队]种树](https://www.luogu.com.cn/problem/P1792) - [P4053 [JSOI2007]建筑抢修](https://www.luogu.com.cn/problem/P4053) - [P2949 [USACO09OPEN]Work Scheduling G](https://www.luogu.com.cn/problem/P2949) - [P3620 [APIO/CTSC 2007]数据备份](https://www.luogu.com.cn/problem/P3620) - [CF436E Cardboard Box](https://www.luogu.com.cn/problem/CF436E)