2.4.17 #

解答 #

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

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

首先我们有一个大小为 k 的优先队列，保证最小值在最前。 接下来我们插入一个元素，可以分成两种情况。

如果插入的元素比最小值还要小，那么这个插入的元素会在之后被删除，原队列中的元素不变。

如果插入的元素比最小值大（或者相等），那么最小值会被删除，留下插入的元素。

于是可以观察到这样一个逻辑，在不断的插入过程中，比较小的元素会被过滤，只留下较大的元素。

那么我们可以把题目转化为：

向一个优先队列插入 N 个元素，保证队列的大小不超过 k，如果超过 k 了就删除最小值。

那么前 k 次插入不受影响，之后的 N-k 次插入就会按照之前说过的流程进行。

最后只留下 N 个元素中较大的 k 个元素，得证。