2.4.17

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

英文版原文是:insert followed by remove the minimum,因此是先插入再删除。

大致上相当于一个缓冲区,把比较大的留下来,比较小的筛出去。

首先我们有一个大小为 k 的优先队列,保证最小值在最前。
接下来我们插入一个元素,可以分成两种情况。
如果插入的元素比最小值还要小,那么这个插入的元素会在之后被删除,原队列中的元素不变。
如果插入的元素比最小值大(或者相等),那么最小值会被删除,留下插入的元素。
于是可以观察到这样一个逻辑,在不断的插入过程中,比较小的元素会被过滤,只留下较大的元素。

那么我们可以把题目转化为:
向一个优先队列插入 N 个元素,保证队列的大小不超过 k,如果超过 k 了就删除最小值。
那么前 k 次插入不受影响,之后的 N-k 次插入就会按照之前说过的流程进行。
最后只留下 N 个元素中较大的 k 个元素,得证。

上一题 下一题