25 匹马 5 条赛道，最快需要几轮求出前 3 名？

请点赞关注，你的支持对我意义重大。 ? Hi，我是小彭。本文已收录到 GitHub · AndroidFamily[1] 中。

前言

大家好，我是小彭。

在计算机面试中，逻辑类题目几乎是大型互联网公司的必考题。由于题目花样百出，准备难度较大，题海战术可能不是推荐的做法。在这个系列里，我将精选十道非常经典的逻辑题，希望能帮助你找到解题思路 / 技巧。如果能帮上忙，请点赞加关注，给小彭一点创作的动力。

系列文章

• 《逻辑 | “我知道你不知道”！》[2]
• 《逻辑 | 德·梅齐利亚克砝码！》[3]
• 《逻辑 | 天黑请闭眼！）》[4]
• 《逻辑 | 赛马！》[5]

1. 题目描述

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

2. 解题关键

2.1 分治思想

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

2.2 代表元法

提示： 若不了解并查集，请务必阅读我之前写过的一篇文章：《数据结构 | 并查集 & 联合 - 查找算法》[6]

3. 解决问题

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

3.1 第一回合

首先，我们将 25 匹赛马分为 5 组，让每组马进行组内比赛，得到组内排名，假设结果为

（此时进行了 5 轮比赛）。因为组内排名第四与第五名不可能竞争全场前三名，所以排除每一组的第四与第五名。

第一回合

3.2 第二回合

第二回合

3.3 第三回合

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

论毕。

我是小彭，带你构建 Android 知识体系。

参考资料

[1]

GitHub · AndroidFamily: https://github.com/pengxurui/AndroidFamily

[2]

《逻辑 | “我知道你不知道”！》: https://www.jianshu.com/p/cab1cc7c235d

[3]

《逻辑 | 德·梅齐利亚克砝码！》: https://juejin.cn/post/6903460612886495245

[4]

《逻辑 | 天黑请闭眼！）》: https://juejin.cn/post/6903524335193948167

[5]

《逻辑 | 赛马！》: https://juejin.cn/post/6903861591188783112

[6]

《数据结构 | 并查集 & 联合 - 查找算法》: https://juejin.cn/post/6875746884397301773