P6033 [NOIP2004 提高组] 合并果子 加强版 题解

· · 题解

前言

抢到最优解了，分享几种做法。

Solution1

思路：

这道题的贪心思路是显然的，就是每次找到最小的两堆然后合并，若使用堆维护，时间复杂度 O(n \log n) 。

但是这道题的数据要求 O(n) 做法，又需要对数据排序，而题目中又有 1 \leq a_{i} \leq 10^{5} ，自然能想到使用桶排序。

流程：

因为数据经过排序，我们发现合并出来的数是单调不减的，于是想到用两个队列维护：q1是排序后的元素，q2维护q1与q2元素相加的和。每次让答案加上两个队列中最小的两数之和，并将结果放到q2队尾。

以上是大多数题解的做法，代码就不放了。

Solution2

思路：

这是第一种做法的优化，我们发现，第一个队列完全可以用桶解决，并且桶还可以解决第二个队列的一部分功能。

流程：

具体来说，初始置 ans=0 ，每次找到桶中最小的两个元素，设他们的和为 sum ，让 ans=ans+sum ，如果 sum \leq 10^{5} ，则将其放入桶中，否则将其加入队列。在遍历完所有桶之后，我们将会得到若干个大于 10^{5} 的元素，此时它们都躺在队列里，我们只需要每次统计出队头两数之和 sum ，让这两个数出队，并更新 ans ，再将 sum 压入队尾，直到队列中剩下一个元素，此时的 ans 即为所求。

为什么这样做是正确的呢？因为队列在任意时刻都单调不减，保证每次在队头的两个元素都是最小的。

对于队列具有单调性的说明：

由于两数之和大于 10^{5} 才会进入队列，这里仅讨论 min \{ a_{i} \} > 5 \times 10^{4} 的情形。

设 q_{i} 是队列中的第 i 个元素，q_{head} 表示队头， q_{tail} 表示队尾。

根据上面的流程：一开始，队列中的每个元素都是序列 \{ a_{n} \} 的两个元素之和，有 q_{i} = a_{i \times 2-1}+a_{i \times 2} .( 下标从 1 开始 )

这里由于事先执行了桶排序算法，所以序列 \{ a_{n} \} 与队列 q 都是有序的，而且有 q_{head} \geq 10^{5}，q_{tail} \leq 2 \times 10^{5}，所以有 q_{head}+q_{head+1} \geq 2 \times q_{head} \geq q_{tail} .

而之后的每一轮出队入队操作，设操作前的队尾为 q_{tail}，操作后队尾为 q_{tail'} 。则有 q_{tail}=q_{head-1}+q_{head-2} \leq q_{head}+q_{head+1}=q_{tail'} .

这就说明了它的单调性。

优化：

实现的时候发现此方法可以 O(1) 统计多个值小于 5 \times 10^{4} 且值相同的 a_{i} 对答案的贡献，减少运行时间。但总时间复杂度仍是 O(n) 。

Code，用时103ms，内存52.38MB。

Solution3

思路：

只看 Subtask 4 的数据范围： 1 \leq n \leq 10^{7}，1 \leq a_{i} \leq 10^{5} 。这意味着平均每个桶有 100 个元素，如果把它们一个一个地进入队列，将会导致大量的重复计算，于是我们模仿桶的方式，用一个数组记录每个数在队列中出现的次数，这样就可以 O(1) 将队列中所有相同值的元素统计完毕。

时空复杂度：

除去读入，这种算法的时空复杂度均是 O(max \{a_{i} \} \ast \log n) 。不过实际表现似乎比这个上界好，限于能力，我无法给出更精确的上界。

Code，用时91ms，内存8.73MB。

注意到 Solution3 在 n \leq 10^{5} 时比 Solution2 更劣，所以我们将两种方法写到一起，便得到最终代码。

Code，用时87ms，内存8.72MB。