题意回顾

有 $n$ 个人，第 $i$ 个人得分 $a_i$。
需要至少发 $k$ 件礼物，但要满足条件：

如果 $a_x \geq a_y$，且 $x$ 没拿到礼物而 $y$ 拿到了礼物，那么 $x$ 会不满意。

要求每个人都满意时，发出礼物的最小数量。

关键观察与条件分析

1. 条件转化

条件意味着：不能出现高分者没礼物而低分者有礼物的情况。

这等价于：存在一个分数阈值 $t$，使得：

• 所有分数 $\geq t$ 的人都拿到礼物
• 所有分数 $< t$ 的人都没拿到礼物

否则，如果有一个分数 $\geq t$ 的人没拿到礼物，而一个分数 $< t$ 的人拿到了礼物，就会违反条件。

2. 问题重新表述

我们需要选择一个分数阈值 $t$，使得：

1. 所有分数 $\geq t$ 的人拿到礼物
2. 拿到礼物的人数 $\geq k$
3. 在满足前两条的情况下，拿到礼物的人数尽量少

核心思路

将所有人按分数从大到小排序。
设排序后的数组为 $b[1..n]$（$b[1] \geq b[2] \geq \dots \geq b[n]$）。

我们要找的礼物集合 $G$ 必须是排序数组的一个前缀（因为如果 $b[i] \in G$ 而 $b[j] \notin G$ 且 $i < j$，那么 $b[i] \geq b[j]$，满足条件）。

因此，问题转化为：找到最小的 $m$ ($m \geq k$)，使得选择前 $m$ 个人作为礼物获得者时满足条件。

处理并列分数

由于有并列分数，我们不能简单取 $m = k$。
考虑第 $k$ 个人的分数 $s = b[k]$：

• 所有分数 $> s$ 的人必须拿到礼物（否则他们会不满意）
• 所有分数 $= s$ 的人中，我们必须选择所有排在 $b[k]$ 前面（包括 $b[k]$）的人

因为如果有某个分数 $= s$ 的人排在 $b[k]$ 前面但没拿到礼物，而 $b[k]$ 拿到了礼物，就会违反条件。

算法步骤

1. 排序：将得分数组 $a$ 从大到小排序，得到 $b[1..n]$
2. 确定关键分数：找到第 $k$ 个分数 $s = b[k]$
3. 计算最小礼物数：
   • 找到最后一个分数等于 $s$ 的位置 $j$（即最大的 $j$ 满足 $b[j] = s$）
   • 答案就是 $j$

正确性证明

• 满足礼物数要求：由于 $j \geq k$，礼物数 $\geq k$
• 满足不满意条件：所有分数 $\geq s$ 的人都拿到了礼物，所有分数 $< s$ 的人都没拿到礼物，因此不会出现高分者没礼物而低分者有礼物的情况
• 最小性：如果我们只发 $j-1$ 份礼物，那么至少有一个分数 $= s$ 的人没拿到礼物，而其他分数 $= s$ 的人拿到了礼物，违反条件

复杂度分析

• 排序：$O(n \log n)$
• 线性扫描：$O(n)$
• 总复杂度：$O(n \log n)$，对于 $n \leq 2000$ 足够快

总结

本题的关键在于：

1. 理解条件等价于礼物集合必须是排序数组的一个前缀
2. 处理并列分数时，必须包含整个分数段直到最后一个与第 $k$ 个分数相同的人
3. 通过排序和简单扫描即可在 $O(n \log n)$ 时间内解决问题