CSP-S 2021 第一轮 第5题：以比较为基本运算，对于2n个数，同时找到最大值和最小值，最坏情况下需要的最小的比

题目

以比较为基本运算，对于 $2n$ 个数，同时找到最大值和最小值，最坏情况下需要的最小的比 较次数为（ ）。

选项

• A. $4n-2$
• B. $3n+1$
• C. $3n-2$
• D. $2n+1$

答案

C

题解

选 C．\(3n-2\)。

把 \(2n\) 个数分成 \(n\) 对：

1. 每对内部比较：共 \(n\) 次，把较大者放入“大数组”，较小者放入“小数组”。
2. 在大数组找最大值：有 \(n\) 个数，需要 \(n-1\) 次比较。
3. 在小数组找最小值：同样需要 \(n-1\) 次比较。

因此总比较次数为 \[ n+(n-1)+(n-1)=\boxed{3n-2}, \] 这也是最坏情况下能够达到的最少次数。

关键是：每对的第一次比较，同时排除了一个最大值候选和一个最小值候选，所以比独立寻找最大值、最小值更省比较。