贪心总结

· · 个人记录

贪心.

以下不特殊说明的话数据范围都是10^5级别

  1. 直觉性质贪心

    这种反而是最多的....直觉越强对这种题的感觉就越好，最难的贪心题大多也是这类.

    只能看着题来了.

    有n个雪球，这些雪球可能属于不同的种类.堆起一个雪人需要三个不同种类的雪球.问最多能堆起多少个雪人.

    直觉告诉我们要先堆大的.于是拿一个堆维护每种雪球的个数，每次取出前三大的堆雪人，堆完放回去.

    正确性的话,如果取了少的，那么后面可能这个多的就无法配对了.考虑一个极端情况是一种有无数个以及其它的有1个.

    你要购买n个物品，其中有一些是特殊物品.每个物品都有一个费用.你有k个购物车，要把这些物品放到购物车里，购物车非空.如果一个购物车里至少有一个特殊物品，那么这个购物车里最便宜的物品半价.求一种方案使得总费用最小.

    考虑一个购物车里如果有一个特殊物品，那么这里就不需要放别的东西了.如果放了别的东西，那么要么它的价格\geq 特殊物品的价格，此时它没有被减价，没有意义;要么它的价格<特殊物品的价格，此时减价会变少，不优.

    于是我们只要把最贵的k-1个特殊物品放到k-1个购物车里，剩下的物品全都放到一个里就好了.如果特殊物品不足k-1个那就全放.

  2. 邻项交换法.

    适合一些最优顺序问题.有时候这个问法可能是隐式的，比如本来要枚举顺序的题这样做完之后就只需要按这个最优顺序跑一下就好了.还是来看一点题来了解.

    有n个罗汉叠起来，每个罗汉有重量w和力量s(均>0).定义一个罗汉的危险值为他上面的所有罗汉的重量之和减去他的力量.安排一个顺序最小化所有罗汉的最大危险值.

    现在假设我们已经有了一个最优顺序，并且我们要证明它是最优的.使用邻项交换法可以在这个过程中得到最优顺序的一个条件.

    考虑从上往下的第i个人和第i+1个人.现在他们的危险值分别是

    d_i=\sum_{k=1}^{i-1}w_k-s_i\qquad\qquad d_{i+1}=\sum_{k=1}^i w_k-s_{i+1}

    如果交换这两个人，那么新的危险值是

    d_i'=\sum_{k=1}^{i-1}w_k+w_{i+1}-s_i\qquad\qquad d_{i+1}'=\sum_{k=1}^{i-1}w_k-s_{i+1}

    显然交换之后对上面和下面的人都没有影响，因为只关心w的前缀和.

    根据最优性，我们得到

    \max(d_i,d_{i+1})\leq \max(d_i',d'_{i+1})

    化简一下得到

    \max(-s_i,w_i-s_{i+1})\leq \max(w_{i+1}-s_i,-s_{i+1})

    然后直接按照\max(-s_i,w_i-s_j)< \max(w_j-s_i,-s_j)重载小于号sort一波就好了.

    为什么呢?因为如果进行冒泡排序的话相当于是进行邻项比较和交换，而因为一些原因，邻项比较可以直接推到任意两个上.

    这个原因是Strict\ Weak\ Ordering，是stl中偏序关系的一个条件.重载的偏序(<)关系需要满足四个条件:

    1. 反自反，a\not <a

    2. 反对称，a<b\Longrightarrow b\not <a

    3. 传递，a<b\ \and\ b<c\Longrightarrow a<c

    4. 不可比传递.定义不可比关系a\neq b为a\not <b\ \and\ b\not <a，那么a\neq b\ \and\ b\neq c\Longrightarrow a\neq c

    下面我们通过改写原比较条件来证明这四个条件满足.

    通过分情况讨论把\max去掉.这里展示两种情况的讨论.

    ①当w_i-s_{j}\geq -s_i,w_{j}-s_i\geq -s_{j}时，有w_i-s_j<w_j-s_i，即w_i+s_i<w_j+s_j.

    ②当w_i-s_j<-s_i,w_j-s_i<-s_j时，有

    \begin{array}{ccc} s_j-s_i>w_i>0\\s_i-s_j>w_j>0 \end{array}

    ​ 此情况恒不成立.

    综合其他两种情况我们得到结论，原条件其实等价于w_i+s_i<w_j+s_j，而这个条件显然满足那四个性质.

    皇后游戏

    占坑待填.

  3. 撤销贪心/模拟费用流

    先说模拟费用流好了.这个其实就是把撤销造成的影响加入贪心的决策里.还是看题.

    区间不超过k段的最大子段和.

    考虑两段最大子段和怎么做.先选出一段最大子段和，然后两段的最大子段和只有两种情况 1. 在第一段之外再选一段 2. 从第一段里面挖掉一部分.这种情况等价于把选取的第一段取负之后再次选择. 于是两段的最大子段和就相当于: 1. 求一段的最大子段和 2. 把求出的这一段取负 3. 再求一次最大子段和并和第一次的相加. 更多段的以此类推，都是上一次求出的最大子段和取负之后再跑最大子段和. 剩下的就是线段树的一坨信息了... $O(km\log n)

    一个n个点的环，每个点有一个价值w，要求选取m个，并且相邻的点不能同时选.

    类似刚才的，我们使用大根堆维护所有点的价值最大值，使用双向链表维护每个点的前驱后继.然后每次取出最大的w_i，然后删除与它相邻的点pre和suc，并令w_i=w_{pre}+w_{suc}-w_i.什么意思呢?就是选择一个选择集合点之后可以反悔选择和它相邻的两个点对应的选择集合.pre和suc维护了相邻点对应的选择集合.双向链表维护的实际上是以某个点为中心的选择集合的相邻关系.每次选取一个点之后将这个集合取反并向左右各扩展一个位置.

    这题可能不太好理解?画一下图就好了.

    还有一种撤销贪心适合于极大/极小满足类的问题.其思想是先不管后面的局面，只考虑尽量满足当前这一个.如果后面满足不了了就考虑从前面的拿出一个不优秀的并使用这个替换前面的.还是看题.

    有n个建筑受到了严重的损伤，需要维修.修复第i个建筑需要t_i的时间，并且如果一个建筑不能在d_i时刻之前修复那么它就报废了，不能再被修复.同一时间只能修复一个建筑，初始时刻为0.求最多能修复多少建筑.

    按d_i从小到大排序，设当前已经使用的时间为tot.考虑第i个建筑，如果tot+t_i\leq d_i那么就修复它，否则，看一下之前修复的建筑里有没有t比它大的，如果有就不去修复那个建筑转而修复当前这个.这样子显然不会使得答案变劣.

    有n头牛，每头牛有一个费用p_i.你有k张优惠券，第i头牛使用优惠券后价格会变成c_i.一头牛只能购买一次.你有m元，问最多能买多少头牛.

    先按c升序排序，把前k小的买掉.接下来尝试购买剩下的n-k头牛.有两种选择，要么不在剩下的牛中使用优惠券，这样我们就购买剩下的牛中p最小的一头；要么使用优惠券，这时候我们需要从使用了优惠券的牛中抽出一个，显然应该抽出p-c最小的那一个，然后再买剩下的牛中c最小的那一个.在两种选择中取一个较小的即可.可以使用三个堆实现.