前言

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

---

系列文章

• 「数理逻辑」| “我知道你不知道”！
• 「数理逻辑」| 德·梅齐利亚克砝码！
• 「数理逻辑」| 天黑请闭眼！
• 「数理逻辑」| 赛马！

【持续更新】

---

1. 赛马

1.1 题目描述

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

1.2 解题关键

• 分治思想

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

• 代表元法

在 并查集（一种数据结构）中，会使用根节点来代表一个集合，这种方法叫做代表元法。我们可以借鉴这种 “代表元” 的思想，让一组马中跑的最快的一匹来代表整组马。

举个例子，给定一组赛马 ，为这组马中冠军马，若有 ，则自然有 （即：如果 B 比 A 组中跑的最快的一匹马还快，则 B 比 A 组所有马都快）。

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

1.3 题解

• 分治

首先，我们将 25 匹赛马分为 5 组：

让每组马进行组内比赛，得到组内排名，假设正好马的快慢与编号一致，即：（此时进行了 5 轮比赛）。

因为组内排名第四与第五名不可能竞争全场前三名，所以排除每一组的第四与第五名。

• 代表元

其次，每一组跑得最快的一匹马作为代表元参与一轮 “代表赛”，假设比赛结果是：。

此时，是代表赛中最快的，所以一定是全场第一名，而

此时，是代表赛中的第二名，最快情况下同时也是全场的第二名，则失去前三名的竞争资格；

此时，是代表赛的第三名，最快情况下同时也是全场的第三名，则失去前三名的竞争资格；

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

• 最后一轮

此时，剩余未知的马为：

加赛一轮，总共进行 7 轮可以选出前三名。

论毕。

---

创作不易，你的「三连」是丑丑最大的动力，我们下次见！