今天训练的时候遇到一道感觉挺适合放在笔试的题目，这里分享给大家。

给定 $N(2\le N\le 5000)$ 个物品，每个物品有红色和蓝色两种款式，对于第 $i$ 个物品，红色款式的美观程度为 $r[i]$，蓝色款式的美观程度为 $b[i]$。所有美观程度都是正整数。

现在想要选择 $X+Y$ 个不同的物品，并且其中的 $X$ 个物品是红色款式，$Y$ 个物品是蓝色款式。请求出最大的美观程度。

对于下面的三个限制，分别设计算法并求解：

限制 $1$（easy）：$X+Y=N,1\le X,1\le Y$，且 $X$ 和 $Y$ 的值由你自行决定。

限制 $2$（medium）：$X+Y=N,1\le X,1\le Y$，且 $X$ 和 $Y$ 的值由题目给定。

限制 $3$（hard）：$2\le X+Y\le N,1\le X,1\le Y$，且 $X$ 和 $Y$ 的值由题目给定。

---

建议先从限制 $2$ 开始想起，不要一口吃一个胖子。。。
并且需要注意时间复杂度，可以认为 $O(N^2)$ 及以下的方法是可以通过的。

---

答案：

限制 $1$：由于 $X$ 和 $Y$ 可以自行决定，所以每个物品选择 $r[i]$ 和 $b[i]$ 中的较大值即可。

如果最终选择了全是一种颜色的物品（例如红色），那么找一个 $b[i]-r[i]$ 最小的 $i$ 改为选择蓝色，尽量减少美观程度的损失。

限制 $2$：评论区给出了 $O(N^2)$ 和 $O(N\log N)$ 的解法，都挺好。

$O(N^2)$ 的解法就是常规的动态规划，用 $f[i][j]$ 表示按照编号顺序选择了 $i$ 个红色款式和 $j$ 个蓝色款式的最大美观程度，状态转移方程即为：

$O(N\log N)$ 的解法需要灵机一动。我们可以分解成两步，第一步选择所有 $N$ 个物品的红色款式，美观程度为 $\sum r[i]$；第二步选择其中的 $Y$ 个物品改变成蓝色款式，每一次改变美观程度会增加 $b[i]-r[i]$。

所以我们对 $b[i]-r[i]$ 进行降序排序，选最大的 $Y$ 个即可。

当然也还有 $O(N)$ 的解法。因为我们只要找出最大的 $Y$ 个（而它们之间的顺序无关），所以可以使用快速选择算法在 $O(N)$ 的时间找出前 $Y$ 大的数。

限制 $3$：我们先考虑选择红色款式的物品。在最好的情况下，我们可以选择到前 $X$ 个红色美观程度最高的物品。

但这些物品中可能有蓝色美观程度也很高的，我们需要放弃其中的一些，再按照红色美观程度接着进行选择。

因此，我们可以得到一个重要的结论：

如果所有的物品已经按照红色款式的美观程度降序排序，即 $r[1]\ge r[2]\ge \cdots \ge r[n]$，并且最后一个选择的红色款式的物品的下标为 $i_{rx}$，那么编号为 $1,2,\dots ,i_{rx}$ 的物品是全部被选择的，要么选择红色款式，要么选择蓝色款式。

证明可以借助上面的分析使用反证法：如果存在某一物品 $j\in [1,i_{rx}]$ 未被选择，而第 $i_{rx}$ 个物品是红色的，那么我们可以改为选择第 $j$ 个物品的红色款式，美观程度不会降低。

这样一来，我们就可以枚举 $i_{rx}$：

• $(1)$ 第 $1,2,\cdots ,i_{rx}$ 个物品中选择 $X$ 个红色款式以及 $i_{rx}-X$ 个蓝色款式；

• $(2)$ 第 $i_{rx}+1,\cdots ,n$ 个物品中选择剩余的 $X+Y-i_{rx}$ 个蓝色款式。

因此，我们可以在 $[X,X+Y]$ 的范围内枚举 $i_{rx}$，对于 $(1)$，它就是限制 $2$，我们可以 $O(n)$ 完成；对于 $(2)$，同样可以使用快速选择算法 $O(n)$ 完成，这样总时间复杂度为 $O(n^2)$。

当然还有更快的做法。枚举 $i_{rx}$ 的过程中，对于 $(1)$，可以看成先选择所有的蓝色款式再将其中的 $X$ 个换成红色款式，这里 $X$ 是定值，因此可以用堆实时维护 $X$ 个最大的 $r[i]-b[i]$。对于 $(2)$，$X+Y-i_{rx}$ 不是定值，但 $(n-i_{rx})-(X+Y-i_{rx})=n-(X+Y)$ 是定值，即我们舍弃蓝色美观程度最低的 $n-(X+Y)$ 个物品，因此可以用堆实时维护 $n-(X+Y)$ 个最小的 $b[i]$。

注意 $(1)$ 是随着 $i_{rx}$ 的递增往堆里添加元素，而 $(2)$ 的随着 $i_{rx}$ 的递减往堆里添加元素，因此遍历两边 $i_{rx}$ 分别计算即可，时间复杂度为 $O(n\log n)$。