NOIP 普及 2018 第一轮 第 9 题：同时找数组最大值和最小值的比较下界

题目

给定一个含 $N$ 个不相同数字的数组，在最坏情况下，找出其中最大或最小的
数，至少需要 $N - 1$ 次比较操作。则最坏情况下，在该数组中同时找最大与
最小的数至少需要（ ）次比较操作。（ $\lceil \rceil$ 表示向上取整，$\lfloor \rfloor$ 表示向下取整）

选项

• A. $\lceil \dfrac{3N}{2} \rceil - 2$
• B. $\lfloor \dfrac{3N}{2}\rfloor - 2$
• C. $2N - 2$
• D. $2N - 4$

答案

A

题解

考点定位

同时寻找最大值与最小值的比较次数。

解题过程

先两两比较，每对中的较大值进入最大值候选组，较小值进入最小值候选组。

• N 为偶数：配对比较 N/2 次，再分别从两组各 N/2 个候选中找极值，各比较 N/2−1 次，共 3N/2−2 次。
• N 为奇数：先用一个数同时初始化最大值和最小值，余下 (N−1)/2 对各比较 3 次，共 3(N−1)/2 次。

两种情况统一为 ⌈3N/2⌉−2，对应选项 A。

这也是最坏情况下的下界：每个非最大值至少要有一次“比较落败”，每个非最小值至少要有一次“比较获胜”，共需消除 2N−2 个候选资格。在对手策略下，只有两个尚未比较过的元素相比较时能一次消除两个资格，这样的比较至多 ⌊N/2⌋ 次；其余比较一次至多消除一个。因此至少需要 2N−2−⌊N/2⌋=⌈3N/2⌉−2 次。

选 A。

易错提醒

统一公式使用向上取整。代入 N=3 时需要 3 次比较，向下取整的错误公式只给出 2 次。