思考分享：如果要25匹马中选出跑得最快的3匹，每次只有5匹马同时

如题，如果要25匹马中选出跑得最快的3匹，每次只有5匹马同时跑，没有计时器情况下最少要比赛几次

有思路的话应该算比较好思考的。

先抛答案，7次

步骤如下：

1. 前五次，25分5组，各赛一次。

2. 第六次，每组第一名赛一次

3. 设第六次比赛后，第一名所在组是A组，第二名为B组，以此类推；再设A组第一为A1，第二为A2，以此类推；易知A1为第一名，只需要A2, A3，B1, B2，C1决胜负，即可得知二三名，此为第七次

用图来表示就很好理解了。

赛了六次之后可以得到下图，A组第一最快，E组第一最慢。1代表当组最快，5代表当组最慢

image.png

接下来剔除“不可能为前三名的选手”

• 每组最后2名
• D、E组全组

image.png

• 仔细思考，B3,C2,C3都不可能为前三

image.png

• 接下来想，A1第一铁板钉钉了，那么A2, A3,B1,B2,C1五匹马再跑一次即可得出前三了

以上是逻辑思考。来看看数学思考

来倒退到第六次比赛，进行数学思考：

image.png

分别连接一下：

image.png

熟悉数学的同学可能就知道了：这不就是个二叉堆嘛？

二叉堆：二叉堆是一种特殊的堆，是一棵完全二叉树或者是近似完全二叉树，同时二叉堆还满足堆的特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆

所以了，这组成了一个二叉堆，还是最大二叉堆，且是一个近似完全二叉树，即任意一个点都比其连接的子节点大（快），其中顶点是A1

换成这道题的语言，就是，第一名是A1的了，由于任意一个点都比其连接的子节点大（快），那么把A1所连接的两个子堆顶点（也就是A2, B1），以及其子节点（A2的子节点为A3,B1的子节点为B2和C1）在比一次，即可得出2、3名了

image.png