题解 CF436E Cardboard Box

· · 题解

最近做到的最难的一题反悔贪心，参考了题解做法才想明白。

解题思路：

考虑反悔贪心。

由于本题要求恰好取到 w 颗星星，不能超过，也不能少，所以思考方向可以应导向为到底怎样得到额外的一星才代价最小：

最简单的决策是直接选择一个一星关卡打了。然后还有以及反悔贪心的基本套路，撤销一个一星关卡的影响，然后再把它改成当前这一个两星关卡的影响。

接下来两种是较难想到的，也是这道题为什么是紫色的这道题真正的难点：撤销一个一星关卡，然后找一个其他的两星关卡打了；把一个两星关卡反悔成一个一星和另一个两星关卡。

首先是撤销一星选两星这个操作，可以考虑这样一种情况：有个关卡一星特别难，但是二星代价很小，另一个关卡一星特简单，但是两星耗时极长，如果只有一开始的两种决策，会出现（假设要得总计两星）选了第一、二个关卡的一星或者是第二个关卡的两星，而无法决策到第一个关卡的两星的情况。换句话说，就是可能出现一星耗时长无法进入决策考虑范围的情况。

举个例子就是：

关卡一：一星 1 单位时间，两星 100 单位时间。

关卡二：一星 99 单位时间，两星 10 单位时间。

一开始的一星决策肯定是选择关卡一的一星。然后到二星决策时，如果只有一开始的两种决策就只会选择关卡二的一星，总代价为 100，实际上直接打关卡二的二星就只需要 10 的代价。

(虽然不太合理，但好像确实没说不能打两星时间比一星短

然后是一个两星关卡反悔成当前关卡一星和另一个两星关卡，这种情况和上一种有点类似，都是因为可能出现直接某一个关卡直接二星很容易，而一星很难，导致无考虑不到的情况，而这一种没有上一种极端，而且有了上一个的基础这一个决策也很好理解，所以直接给出例子：

假设你要拿到三星

关卡一：一星 100 单位时间，两星 10 单位时间。

关卡二：一星 5 单位时间，两星 8 单位时间。

这样第一次和第二次决策时分别是选择的关卡二一星和两星，没有涉及关卡一，而总共二星时在要取得一颗星按照之前的三种决策只能取关卡一的 100 单位时间，与最优的 15 单位时间相差甚远。

实现上，可以重新列出上面的几种决策（其实是我数不过来到底要维护多少堆了），并依次分析需要维护的值，当然还是正常反悔贪心的堆维护。

具体的，有：

  1. 打一个从来没有打过的一星关卡，需要维护从没有打过的关卡的 a_i 的最小值。

  2. 把一个打过的一星关卡变成同关卡二星关卡，需要维护已经打过一星的关卡的 b_i-a_i 的最小值。

  3. 把一个打过的一星关卡变成一个其他的二星关卡，需要维护 b_j-a_i 的最小值，实际上就是维护两个值：即已经打了的一星关卡的 a_i 的最大值（或者说是 -a_i 的最小值，两者等价），和从来没有打过的关卡的 b_j 的最小值。

  4. 把一个已经打过的二星关卡反悔成当前一星关卡和一个从没有打过的二星关卡，需要维护 a_i-b_i+b_j 的最小值。类似的，拆分下来的就是一个已经打过两星关卡的 a_i-b_i 的最小值和从没有打过的关卡的 b_i 的最小值。

其中决策四 中要维护的从来没有打过的关卡的 b_i 的最小值在决策三 中也用到了，所以你只需要维护五个堆就可以啦。

然后每一次决策根据贪心的原则从所有的决策中选择一个耗时最短的即可，注意需要。

细节上：每一个堆不仅要注意维护取得是哪一个值，还要考虑到维护的是哪一些类型里的值，比如“从没有打过的关卡”“已经拿了两星的关卡”等。