NOIP 提高 2014 第一轮 第 12 题：同时查找 2n 个数中的最大值和最小值，最少比较次数为（ ）.

题目

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

选项

• A. $\dfrac{3(n-2)}{2}$
• B. $4n-2$
• C. $3n-2$
• D. $2n-2$

答案

C

题解

考点定位

本题考「最大最小值比较下界」,对应大纲 4.1.1 复杂度（难度【3】）。

解题过程

2n 个数：先两两配对 n 次比较，胜者组找最大 n−1 次、败者组找最小 n−1 次：

$$n+(n-1)+(n-1)=3n-2$$

选 C。

易错提醒

① 配对法是下界且可达；② 朴素法 4n−3 量级不是最优。