简介
还没有简介
大概就是当前选择不会对后续选择造成影响的情况下尽量选取当前最优的选择
几类常见的结论
将 $n$ 个物品分成 $k$ 组，第 $i$ 组有 $cnt_i$ 个，第 $i$ 组的贡献为 $\sum_{i=1}^{cnt_i} i\times a_i$
结论：每组个数相差不超过 $1$
将 $n$ 个物品按价值排序，要求选择 $k$ 个物品，需保证这 $k$ 个物品不相邻且价值和最大
结论：从大到小能选则选
在 $n$ 个盒子中总共放 $m$ 个球，第 $i$ 个盒子中放入 $j$ 个球的贡献是 $f_ja_i$，$f_i$ 单调递增且 $f_{i+1}-f_{i}$ 也单调递增，求如何分配 $m$ 个球使得总贡献最小
结论：每个球单独放，用小根堆存储当前放入一个球后贡献最小的盒子，依次放入即可
几类比较常见的贪心
排序贪心
题目要求对一个序列求一个最优值，序列的最优值取决于每个元素计算的顺序
我们只需列出 $i$ 排在 $i+1$ 的条件按照这个条件排序即可
简要题意：给定 $n$ 个数对 $(m_i,p_i)$，现在要求选择尽量多的数对，不妨设选择了 $2\times k$ 个，则需保证恰好有 $k$ 个数对取第一位 $m_i$，同时恰好有 $k$ 个数对取第二维 $p_i$，且需保证 $\sum m\ge \sum p$，求最多取多少个数对
$n\le 10^5$
简要题解：我们不妨假设一定取 $(m_1,p_1)$ 和 $(m_2,p_2)$ 这两个数对，那么谁应该取第一维，谁应该取第二维，我们简单列一个不等式容易得到当 $m_1+p_1\ge m_2+p_2$ 时我们一定取 $m_1$ 和 $p_2$
那么我们考虑先将所有点排个序，那么我们最终的选择中，取 $m$ 的一定都在取 $p$ 的前面，我们考虑二分答案 $x$，然后我们枚举一个分界点 $i$，对于 $[1,i]$ 我们取 $k$ 个 $m$，对于 $[i+1,n]$ 我们取 $k$ 个 $p$，这里我们用两个堆维护前 $k$ 小和前 $k$ 大即可，时间复杂度 $O(n\log^2 n)$
2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020) L Neo-Robin Hood
排序贪心进阶版，树形排序
简要题意：现在有一个长度为 $n$ 的字符串，我们现在要将它的所有前缀按照某种顺序排成一排，如果前缀 $i$ 排在第 $j$ 个位置，那么它的代价为 $j\times a_i$，求最小贡献和，如果 前缀 $i$ 是前缀 $j$ 的 $border$，那么前缀 $i$ 一定要排在前缀 $j$ 的前面
$n\le 10^5$
简要题解：我们考虑 $kmp$，建出 $fail$ 树，那么如果想要排点 $u$，则必须先排它的所有父亲
我们考虑对于两个不相交的集合 $S,T$，不妨令 $S$ 的大小为 $sz_S$，$S$ 的 $a$ 之和为 $sum_S$，那么我们将 $S$ 排在 $T$ 之前的条件是 $sz_S\times sum_T<sz_T\times sum_S$，等价于 $\frac{sz_S}{sum_S}< \frac{sz_T}{sum_T}$
然后我们考虑，我们在排序过程中的集合会是什么样的，注意到显然是一棵树，那么做法就呼之欲出了，我们用小根堆维护现在的所有的集合，小根堆的权重就是 $\frac{sz}{sum}$，每次取出最小的集合，将其向上合并一次，每个集合的维护我们可以使用并查集，时间复杂度 $O(n\log n)$
传统贪心
凭直觉得到答案