NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 12 题

同时查找 $2n$ 个数中的最大值和最小值，最少比较次数为（ ）.

这题考最值查找优化。拿到题别想朴素法，直接分组：把 2n 个数两两配对，每对内部先比一次分出大小，剩下的 n 个大的找最大、n 个小的找最小，这样总比较次数就是 n+(n-1)+(n-1)=3n-2，选 C。

最容易掉进朴素比较的陷阱：以为每个数都要和当前最大值、最小值各比一次，那样就是 2n-2 次，正好对应选项 D，这是命题人最爱挖的坑。还有人会纠结要不要先整体排序再取首尾，那样比较次数远超 3n-2，完全没必要。记住核心：两两配对后，大的只负责和更大的比，小的只负责和更小的比，互不干扰，这样才省比较。

找最大最小值（分组法）

这题考查的是如何在一次遍历中同时求出最大值和最小值，核心在于分组比较，用更少的比较次数完成两个目标。

1. 朴素做法的代价

如果按常规思路，初始化 max 和 min 为第一个数，然后从第二个数开始，每个数都要和当前的 max、min 各比一次：

• 第 i 个数：与 max 比 1 次，与 min 比 1 次 → 2 次比较
• 共 2n 个数，但第一个数不用比，所以总比较次数是 2(n-1) = 2n-2。

这个结果正好对应选项 D，也是很多同学会选错的答案。命题人故意放这个选项，就是想看看你是否意识到“同时找最大最小”可以比“分别找再合并”更省比较。

2. 分组法的思路

把 2n 个数两两配对，共得 n 对。对每一对先做一次比较：

• 较小的数归入“候选最小值集合”，
• 较大的数归入“候选最大值集合”。

这一步用了 n 次比较。

现在，候选最大值集合里有 n 个数，候选最小值集合里也有 n 个数。要找整个序列的最大值，只需在候选最大值集合里用 n-1 次比较；同理，找最小值只需在候选最小值集合里用 n-1 次比较。

3. 总比较次数

把三部分的比较次数加起来：

• 配对比较：n 次
• 找最大值：n-1 次
• 找最小值：n-1 次

总计：n + (n-1) + (n-1) = 3n-2。

这就是理论上的下界，无法再优化了。所以正确答案是 C。

4. 易错点提醒

• 别被“每个数都要和 max、min 比”的直觉带偏，那样就是 2n-2，是陷阱选项 D。
• 别想着先整体排序再取首尾，排序本身的比较次数远大于 3n-2，完全没必要。
• 分组法的精髓在于：两两比较后，大的只和更大的比，小的只和更小的比，互不干扰，这才省出比较次数。

5. 考频与趋势

基础算法里“同时找最大最小值”的优化思路是高频考点。从题库统计看，基础算法共考过 30 题，覆盖 3 个级别（2007-2025），逐年分布：2007 年 2 题、2008 年 1 题、2009 年 4 题、2010 年 4 题、2011 年 5 题、2012 年 1 题、2013 年 1 题、2014 年 2 题、2016 年 1 题、2019 年 1 题、2021 年 4 题、2024 年 2 题、2025 年 2 题。分赛事来看，NOIP 提高组初赛 13 题、CSP 提高级 9 题、NOIP 普及组初赛 8 题，说明这个考点在提高组尤其重要，命题人常把它放在单选里考最值优化的本质。

6. 预测

基于上述数据，未来提高组初赛仍可能继续考查“同时找最大最小值”的最优比较次数，或者稍作变形（如同时找最大、最小和次大），但核心思路不变：分组比较、分别处理。暂无足够依据预测具体年份或题型变化，建议重点掌握分组法的推导过程，确保一眼看出 3n-2 的来源。