NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 9 题

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

这题考的是‘配对法’求最值。拿到题先想：一次比较能同时给出大小关系，能不能把找最大和找最小‘捆’在一起做？核心就是两两配对，每对内部比1次，再把所有‘大’的找最大、所有‘小’的找最小，最后处理奇数项。

最容易掉进C选项的坑，以为‘先找最大再找最小’就行。但题目问的是‘至少需要’，即最优算法。朴素做法浪费了大量已知的比较结果（比如A>B且A>C，B、C之间其实没比过，但最大值已经锁定为A，最小值只能在剩下的里找），导致总次数变成2N−3甚至2N−2。另一个坑是取整符号：奇数N时配对法需要向上取整，选B的人往往把天花板函数看错成地板函数，少算一次比较。

考点与概念

这题考查的是分治思想和信息复用：一次比较不仅告诉我们谁大谁小，还同时为‘找最大’和‘找最小’提供了线索。如果分开做，这些线索就被浪费了。

命题视角

命题人喜欢挖两个坑：一是让你用‘先最大后最小’的朴素思路，二是混淆向上取整和向下取整的公式。正确答案A是经典结论，但很多人会惯性选C（2N−2）或B（用地板函数）。记住：题目问‘至少’，就是求最优算法。