CSP-S 提高级 · CSP 2021 提高级第一轮 第 5 题

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

拿到题先别急着套公式，想想怎么让比较次数'复用'。核心心法是两两配对：把2n个数分成n对，每对内部比一次分出胜者（候选最大）和败者（候选最小），剩下的问题就简化成在n个胜者里找最大、在n个败者里找最小，这样就能把原本需要分别遍历的开销砍掉一大截。

最典型的坑就是思维定势：学生习惯'先找最大再找最小'，以为这是标准流程，结果算出来是(2n-1)+(2n-2)=4n-3，直接掉进选项A的陷阱。还有人会忽略'同时'这个条件，觉得可以分步做，其实分步做多了重复比较。另外，有些同学看到3n-2觉得太巧了，怀疑是不是漏加了常数，容易误选B（3n+1），那是把配对那一步的n次比较和后续找极值的n-1次比较搞混了，导致常数项错误。

这道题考查的是基础算法中的比较策略优化，具体涉及贪心/分组思想以及最坏情况下的比较次数下界。命题人喜欢在这种'同时求两个极值'的题目里挖坑，因为直觉上大家会觉得分别求最大和最小是理所当然的做法，但竞赛的核心就在于打破直觉，利用比较结果的信息复用。对于2n个数，如果直接先找最大（2n-1次）再找最小（2n-2次），总共要4n-3次，这显然不是最优的，而且选项A就是专门针对这种错误思路设的。真正的突破口在于'两两配对'：将2n个数分成n对，每对内部比较1次（共n次），每对产生一个较大值和一个较小值。此时，最大值必然在n个'较大值'中，最小值必然在n个'较小值'中。接下来，在n个较大值中找最大值只需n-1次比较，在n个较小值中找最小值也只需n-1次比较。把这三部分加起来：n + (n-1) + (n-1) = 3n-2。这个策略之所以成立，是因为每对内部的比较已经帮我们排除了另一半元素参与后续极值竞争的可能性，从而大幅减少了总比较次数。这也是信息学竞赛中经典的'锦标赛'思想。关于选项B（3n+1），它比正确答案多了3次，通常是因为学生误以为配对那一步需要额外比较，或者在计算n-1时不小心加了常数，属于典型的计算失误。从考频数据来看，'基础算法'这一大类在题库中已考过30题，覆盖2007年至2025年，其中2021年考了4题，2024年和2025年各考了2题，说明这类题目是高频考点，且近年来在CSP提高级和NOIP初赛中都频繁出现。命题趋势上，这类题目往往不会单纯考公式，而是结合具体场景（如数组操作、链表遍历）来考察学生是否真正理解分组策略的本质。因此，面对此类题目，拿到题后第一反应应该是'能不能两两配对？'，如果能，就立刻想到3n-2这个结论；如果不能配对（比如奇数个元素），则需要特殊处理。总之，这道题的答案C（3n-2）是经过理论证明的最优解，任何试图用简单遍历的方法都会导致比较次数增加，而选项D（2n+1）更是完全偏离了比较次数的量级，属于干扰项。