前言

USACO Training 1.3的题目中出现了两题涉及到贪心思想，思路都比较简单，但是贪心策略呢，还是蛮难的一个东西，本文主要稍微介绍一下贪心中的一个比较重要的思想：等值性，当然还有一些题目会涉及等价性，但是通过转化还是会变成一个等值性的问题，我尽量挑选一些比较简单的题目阐释一下什么是等值性，以及这个性质在解题过程中一般会有什么用

题意

[Mixing Milk]

给出牛奶制造公司每日的牛奶需求，以及每个农民的可提供的牛奶量和每加仑的价格，计算牛奶制造公司所要付出钱的最小值

解题思路

拿到这个题，可能非常容易得到思路，将牛奶价格从低到高排序，依次购买

原理呢，就是等值性，所有牛奶都是一加仑一加仑出售的，如果买了价格高的一加仑，为何不用价格低的一加仑去替代呢，可能对贪心有所涉猎的同学会知道，这还有一个解释，就是等值性符合贪心的法则，局部最优解导向全局最优解

那如果每个农民的牛奶是盒装的，每个农民的包装盒大小不一，必须整盒购买，那这个时候还能采用这种贪心策略么，肯定就不行了，因为不具备等值性的情况下这种贪心策略无法保证无后效性，子问题的决策影响了全局最优解，举个极端的例子，你买最便宜的牛奶，结果一盒容量特别大，导致超出了你的牛奶需求，虽然单价便宜，但是花费的总价格还是多的，这种问题是动态规划中的背包问题，有兴趣的同学可以自己先了解，此处不详细展开

更多的例题

酸奶工厂

题意

奶牛们收购了一家世界著名的酸奶工厂YuckyYogurt. 在接下来的N周, 牛奶和人工的价格每周会波动，第$i$周公司能够以$C_i$美分一单位的价格来生产酸奶。Yuckyfactory被奶牛们照顾得很好，所以每周可以生产很多单位的酸奶，YuckyYogurt 拥有一个仓库，可以以S美分每单位每周的价格储存没用的酸奶。神奇的是，酸奶不会变质。而且仓库十分巨大，可以容纳很多牛奶，YuckyYogurt 每周要交付$Y_i$单位的酸奶给它的客户。请你帮助奶牛们减少整个N-week期间的支出. 第i周生产的牛奶和之前储存的牛奶都可以用来交第i周的货

解题思路

首先我们寻找题目中的等值性。需要交付的酸奶，这是等值的，也就是说，我只要知道，每单位酸奶在交付那个时刻的最小成本就可以了。

那么交付时刻的成本是怎么计算的呢，是酸奶生产时的价格$C_j$，加上生产时刻$j$到交付时刻$i$的保存时长所产生的费用$S*(i-j)$

我们其实可以按周维护这个最小成本，比如说，第$i$周最小成本为$x$，那么第$i+1$周的最小成本，不是$x+s$就是$C_{i+1}$，则可以对最小成本进行更新$x=min(x+s,C_{i+1})$，每周按照更新的最小成本计算交付代价即可

日光浴

题意

有$C$头奶牛日光浴，第$i$头奶牛需要$minSPF_i$和$maxSPF_i$ 单位强度之间的阳光，第$i$头奶牛在日光浴之前必须涂抹防晒霜，一共有$L$种防晒霜，涂上第$i$种晒到身上的阳光强度就会稳定为$SPF_i$，第$i$种防晒霜有$t_i$瓶, 问最多可以满足多少头奶牛日光浴

解题思路

我们先简化一下题意，题目的本质是用$C$个区间去匹配$L$种点，每种点有$t_i$个，最多能匹配几对

贪心问题很多都会涉及到区间，一般的处理方法是，先对区间进行排序（左端点，右端点，或者双关键字等）

这道题期望的是最多的奶牛能够日光浴，也就是说最多的区间被匹配，即区间等值，那我们先随便定一个顺序：从左到右去利用这些点匹配，那么区间排序要按照右端点从小到大排序，每次直接选取区间内最小的点去匹配

其实上述的语句就是这道题的题解了，为什么呢

  1. 假设区间内两点坐标 x < y，则随着区间右端点的递增，只会出现 x 不能匹配而 y 依然能匹配的情况，不会出现 y 不能匹配而 x 依然能匹配的情况，因此选择 x 更优
  2. 因为区间的被满足是等值的，因此能够匹配上就直接匹配，对答案贡献均为1

如果难以理解，可以尝试画图，可能更容易理解区间之间的关系

工作安排

题意

一共有N件工作，完成每件工作均只需要一单位时间，每件工作都有对应的Deadline和报酬，问能取得的最大报酬

解题思路

先直接讲一下做法

按照Deadline进行排序，如果一个任务能够在Deadline之前被执行那么执行并得到其价值，当发现当前处理到的时间点迟于一个任务的Deadline，找到之前执行任务中价值比其小的价值最小的任务放弃，选择完成当前任务即可

可能你已经有点感觉，为什么可以替换任务呢，因为任务等价，这里的价指代价，即一单位时间。条件允许的情况下，相同的时间，可以用来换取更高的价值

这个替换操作，用优先队列(STL::priority_queue)维护选取的任务即可

总结

关于等值性和等价性的贪心问题其实有不少，有的时候也会掺杂在其它的算法问题中作为一个子问题，用优先队列去做退流操作也比较常见 （有的情况甚至会需要双优先队列或者是更高级的数据结构来维护这种等值性），需要注意的是，等值并非只有单个点的替换，有时也会有多点等值替换的情况（BZOJ 2151）