第三周的贪心章节除了几个区间的题都较容易。

A 空隙计数

一些整数区间，区间端点均非负，每个区间对应一个任务，要求电脑在这个区间完成任务，完成时间为1单位时间且必须从整数时间点开始任务，保证输入满足有解。

求完成所有任务的最少空隙。

题解

左端点升序排列，然后再按右端点升序排列，从左往右考虑。right保存了当前连续工作时间最右可以达到的时间我们考虑局部：由于必然有解，两个区间不可能为相同且间隔为1的区间下面详细讨论x区间和y区间三种情况：

  • 相交或包含：总不存在间隙，此时right＞y.left，但是right指针需要向右移动一位（保证有解），特别地right=y.right时，不需要移动，因为对应的两个工作单位时间必然贴着靠右。
  • 相切：总不存在间隙，此时right=y.left，但是right指针需要向右移动一位（保证有解）。
  • 相离：必然存在间隙，此时right<y.left，right=y.right，空隙计数+1

总结：区间问题通常需要讨论区间端点大小比较。

B 屠龙骑士

龙n个头及对应头的大小，m个骑士及对应高度。每个骑士可以砍掉不大于它身高的头且只能砍一次，且每次砍头需要付与高度相同的金币。

求花费最少的金币，如果无法屠龙则输出'Loowater is doomed!'。

题解

头和骑士都按大小升序排列，遍历两者，当某个骑士满足条件则立即征用，如果所有头都被看下则返回身高求和，否则输出'Loowater is doomed!'。

正确性证明。如果不选择最小的我们可以证明最后和一定不少于当前情况：因为后面的头严格递增，上一个没有被选择的最小的骑士不高于该头大小，所以求和不少于选择最小的情况。

C 鞋匠做鞋

有n个订单，每个订单有完成所需时间和每推迟一天开始的罚款。

罚款最少的订单完成顺序，多种解法输出字典序第一个。

题解

按照罚款/完成时间降序贪心，正确性证明：交换最优解的相邻两个，可以得到罚款变多。交换不相邻的两个可以看作多次相邻交换。

D 矩阵最大和

一个元素为整数的矩阵。

使得矩形区域子矩阵最大和。

题解

比较容易想的是先求出(1,1)到其它点围成矩形的和，然后再用求交集公式求出每一种可能矩形区域的和，复杂度为O(n4)O(n^4)，但也能AC。另一种方法是合并多行然后求最大子序列，合并可以在循环右下角边界时同时进行所以复杂度为O(n3)O(n^3)。

复习一下求最大子序列：s为前i个序列以第i个数结尾的的最大子序列，如果s>=0那么可以再往上加数，s<0说明肯定不能取，s=当前数。

E 售货顺序

一些商品的利润和对应售卖有效时间，每个商品售卖需要1单位时间，选择一些商品按一定顺序售卖且不超过售卖有效时间。

求利润最大值。

题解

首先我们发现所有商品售卖有效时间最大值就是我们最多可以售卖的商品数量，我们从大到小对有效时间遍历，每个有效时间可以卖的都取利润最大的（注意有效时间大的可以到小的时间卖），或者说我们将利润升序排序，然后尽可能晚卖，具体使用并查集实现（初始每个点父节点为i每次find操作都指向前一个节点直到为0则不可以再卖东西）。使用反证法证明正确性。

F 车的摆放

n×n的棋盘，摆放n个车，每个棋子都各自给出的一个矩形范围中。

求出车互相不能攻击的摆放方式，如果不存在解法则输出IMPOSSIBLE。

题解

行和列问题相同可以分开考虑，化为区间贪心问题，比较端点大小。如果从左往右考虑显然我们需要让每个区间车摆放靠最左。故先按左端点排序，再按右端点排序（区间小的先摆放），然后靠左端点摆放。每次维护变量left，初始化为第一个区间左端点位置

  • y.right>left，left变为left+1和y.left较大的那一个
  • 否则不存在、

↑然后发现不对，如果[1,4]、[1,4]、[2,2]会导致[2,2]无解。更改排序顺序，先按右端点排序，再按左端点排序（左端点其实无所谓按什么顺序比较），然后取消使用left，改成每次都要扫描区间是否可行。

总结：关键是如何想出所有可能的例子以及为何从右端点排序就可以：由于我们贪心规则是左起第一个，按左端点排序可能会挡到后面的但其实还能排到其他地方，但按右端点排序就不会挡到其它区间。

G 均值为一

n个整数，加上k个非负数数使得该数列平均数为1。

k最小值。

题解

平均数>=1则k=sum-n，若k>0全取0；平均数<1则k=1，取n+1-sum

H 图片变色

四个像素用小写字母表示颜色，一次操作可以同时改变不超过两个像素为一个颜色。

最少操作次数使图片像素均为一个颜色。

题解

直接暴力分类讨论：

  • 全相同：0次操作
  • 1：3比例：1次操作
  • 2：2比例：1次操作
  • 1：1：2比例：2次操作
  • 1：1：1：1比例：3次操作

优化：操作次数为颜色种类-1

如果不能暴力该怎么做？

I 最小子序列分割

给出序列，求一个子序列和它的补，使其中一个子序列字典序最小。

满足要求的子序列和它的补，要求字典序小的子序列靠前。

题解

直接取字符串最小字母作为第一个输出。

注意aaa这种可能会有重复情况需要考虑。

如果不能暴力该怎么做？这里print any刚开始还以为是只输出一种，属于吃了英语的亏了。

J 屠龙（梅开二度）

桐老爷只有在比龙力量大才能击败龙，击败后可以获得相应力量。给出桐老爷初始力量和n条龙的力量和对应的奖励力量。

如果桐老爷能击败所有龙则输出YES，否则输出NO。

题解

怎么还跟龙干上了。将龙按力量升序排序，然后桐老爷按顺序和龙比较力量，若成功则获得奖励并继续比较，直到遍历结束，如果指针>n则成功击败，否则失败。正确性证明：无所谓龙是否可能力量相等，因为交换两者顺序结果不会变化。所以我们考虑龙力量递增上升序列，我们证明如果按规则失败则其它任何顺序都不可能击败。替换接下来无法击败的龙和某条龙的顺序，显然我们要替换比当前龙小的龙，因为更大的肯定也失败。替换后，我们在之前遇到这条龙就无法击败了，因为根据题目那时候桐老爷力量不高于当前桐老爷力量，矛盾，得证。