请点赞关注，你的支持对我意义重大。

1. 题目描述

给定 25 匹马与 5 条赛道，一个赛道只能容纳一匹马，每轮比赛只能得到 5 匹马之间的快慢程度，而不是速度，求决胜 1，2，3 名至少多少轮。

2. 解题关键

2.1 分治思想

欲求得 25 匹马中的前三名，可以先求得较小规模问题中的前三名，再合并小规模问题的解得出最终解。

2.2 代表元法

在并查集（一种数据结构）中，会使用根节点来代表一个集合，这种方法叫做代表元法。我们可以借鉴这种 “代表元” 的思想，让一组马中跑的最快的一匹来代表整组马。举个例子，给定一组赛马 $A_1,A_2,A_3,A_4,A_5$，$A_1$为这组马中冠军马，若有 $B_1>A_1$，则自然有 $B_1>A$（即：如果 $B_1$ 比 $A$ 组中跑的最快的一匹马还快，自然可以得出 $B_1$ 比 $A$ 组所有马都快的结论）。

3. 解决问题

理解了分治和代表元后，现在可以说问题的解法了，一共分为 2 个回合来解决：

3.1 第一回合

首先，我们将 25 匹赛马分为 5 组，让每组马进行组内比赛，得到组内排名，假设结果为 $A_1>A_2>A_3>A_4>A_5$（此时进行了 5 轮比赛）。因为组内排名第四与第五名不可能竞争全场前三名，所以排除每一组的第四与第五名。

KaTeX parse error: Expected 'EOF', got '组' at position 3: A 组̲：\{A_1,A_2,A_3,…

KaTeX parse error: Expected 'EOF', got '组' at position 3: B 组̲：\{B_1,B_2,B_3,…

KaTeX parse error: Expected 'EOF', got '组' at position 3: C 组̲：\{C_1,C_2,C_3,…

KaTeX parse error: Expected 'EOF', got '组' at position 3: D 组̲：\{D_1,D_2,D_3,…

KaTeX parse error: Expected 'EOF', got '组' at position 3: E 组̲：\{E_1,E_2,E_3,…

第一回合

3.2 第二回合

其次，每一组跑得最快的一匹马作为代表元参与一轮 “代表赛”，假设比赛结果是：$[A_1>B_1>C_1>D_1>E_1]$，由此可以排除失去竞争资格的赛马：

• $A_1$ 是代表赛中最快的，所以 $A_1$ 一定是全场第一名；

• $B_1$ 是代表赛中的第二名，最快情况下 $B_1$ 同时也是全场的第二名，则 $B_3$ 前面还有 $B_2$，所以 $B_3$ 失去竞争前三名的资格；

• $C_1$ 是代表赛中的第三名，最快情况下 $C_1$ 同时也是全场的第三名，则 KaTeX parse error: Expected '}', got '、' at position 5: {C_2、̲C_3} 失去前三名的竞争资格；

• $D_1$ 和 $D_1$ 是代表赛的四五名，说明 D 组和 E 组都失去了前三名的竞争资格；

第二回合

3.3 第三回合

此时，剩余的未知顺序的赛马正好有 5 匹，加赛一轮就可以得出第二名和第三名的归属。三个回合总共进行了 7 轮比赛，故答案就是 7。

$\{A_2,A_3\}$

$\{B_1,B_2\}$

$\{C_1\}$

论毕。