CF436E Cardboard Box 题解

0htoAi · 2021-12-23 21:00:50 · 题解

前言：借鉴了 @George1123 的做法，在此基础上改良，另外变得好理解了。经过改良，我的做法比他的做法快了 4 倍，目前是最优解。

大体思路：

需要权衡的是直接花 b_i 得 2 个星星还是花 2 个不同的 a_i 得 2 个星星，如何对比这两种情况哪个更优是最大的问题。

开 2 个小根堆维护 a_i 和 b_i 的最小值，然后开始贪心。

贪心过程：

目的是要选当前最优，设当前 q_a 堆的最小值为 a_{min}，q_b 堆的最小值为 b_{min}，可以假设它们不是同一个 i。

显然直接比较 \frac{b_{min}}{2} 和 a_{min} 的大小是不对的，因为可能 a_{min} 所对应的 b 的值比 a_{min} 大不了多少。

于是又取出 q_a 堆除去 a_{min} 的最小值 a_{min2}，也可以假设 a_{min2} 与 b_{min} 不是同一个 i。

现在可以直接比较 a_{min}+a_{min2} 和 b_{min} 的大小了。因为现在要选 2 个星星出来，这两种必定有一种是最优情况。

考虑分类讨论：

• （注：取等时无论怎么处理结果一样） 连取 $2$ 个 $1$ 星更优，答案加上 $a_{min}+a_{min2}$，用到 $a_{min}$ 和 $a_{min2}$ 所对应的 $i$ 的次数各增加 $1$。 对于 $a_{min}$ 和 $a_{min2}$ 所对应的 $2$ 个 $i$，如果 $i$ 是第一次被用到，那么 $q_a$ 堆中还要新加进一个权值为 $b_i-a_i$ 的星星，表示可以增加 $b_i-a_i$ 的代价多得到 $1$ 个星星，跟普通星星无差异。 此时注意，要在 $q_b$ 堆中删除 $i$ 这个点，因为它已经不能一次取 $2$ 个星星了，可以用堆的常用操作懒删除，等 $i$ 到堆顶的时候再删。
• 直接取 $1$ 个 $2$ 星最优，答案加上 $b_{min}$，用到 $b_{min}$ 所对应的 $i$ 的次数为 $2$。 将 $a_{min}$ 和 $a_{min2}$ 重新入 $q_a$ 堆，在 $q_a$ 中删除 $b_{min}$ 所对应的点，同理也可以使用懒删除。

小细节：

• 因为每次贪心都是取 2 个星星，如果 w 为奇数该怎么办？

  如果 w 为奇数则在最开始向 q_a 增加一个编号为 0，权值为 0 的点，相当于白送一个星星，并将 w 变成 w+1。注意这个 0 号点要标记为使用过一次，以免再次入堆。

• 特判掉这种情况，如果遇到了直接全选 $b_i$ 就好。