100匹马，4个赛道，找出跑最快的4匹马。

前言

其实在网上也有不少该题目的文章，但是可能题目不一样，能找到的题目名为《64匹马，8个赛道，找出跑得最快的4匹马》。该题目出现在腾讯的面试题里面。

最近我也在进行腾讯的面试，也遇到了这一题，虽然网上有答案，但是还是想写一些我的思路，或许不是最好，希望有人可以点评一下。

题目

100匹马，每一只马的跑步速度是恒定的，不会因为多跑几轮就会速度下降，没有提供秒表进行记录。问需要比赛多少轮才能得出最快的4匹马?

解题思路

第一轮：从100匹马分成25组，每组4只马进行第一轮的比赛，得出每一组第一名的马进行第二轮。第一轮需要比赛25场。

第二轮：我们将第一轮分为ABCDEG...共25组，在第二轮中，取前4组的第一名进行第二轮的第一场比赛。每一场的比赛中的第一名晋级第三轮，第二名会进行第二场，从第一轮晋级的马匹中选取3匹进行下一场比赛，剩下3，4民直接淘汰。

晋级 留 淘汰

1. 25 - 4 = 21 1 1 2
2. 21 - 3 = 18 1 1 2
3. 18 - 3 = 15 1 1 2
4. 15 - 3 = 12 1 1 2
5. 12 - 3 = 9 1 1 2
6. 9 - 3 = 6 1 1 2
7. 6 - 3 = 3 1 1 2
8. 3 - 3 = 0 1 0 3

第三轮：假设通过第二轮得出来的是ABCDEFGH组的第一名，那么我们将要在第三轮决出4强。

1. ABCD 第一组
2. EFGH 第二组

假设第一场AB是第一二名，第二场EF是第一二名，那么将交叉再比赛一次。

1. ABGH
2. EFCD

从而得出最终四强就是第一第二场的前两名。假设是ABEF这个4个。

第四轮：得出的4强当中，进行一次比赛，在第四轮就能提前锁定第一名，假设我们为第三轮的得出的4强重新编号，ABCD，那么进行比赛

1. ABDC

假设胜出的是A，那么ABCD所在的第一轮比赛的组别进入第五轮。还记得第一轮比赛是4匹马为一组，为什么需要这么做呢，因为没有秒数的条件，所以你并不能确定A组第二名是不是一定比B组第一名慢，所以必须进行第五轮，但是为什么只拿这4组呢，因为如果A组第一名已经比H组的第一名快，所以H组后面的所有马都不可能比ABCD组的第一名快，如果B组的第二名比C组的第一名快，那么H组的第一名更加不可能比B组第二名快，所以才将最后得出最快的4个分组的第一名中，将所在的组别放到第五轮进行再一次比赛。

第五轮，因为第四轮得出第一名，假设为A组的第一名。那么剩下的马匹分布如下：

• A2 A3 A4
• B1 B2 B3 B4
• C1 C2 C3 C4
• D1 D2 D3 D4

数字代表的是所在组在第一轮的比赛中的分组排名，所以进行一场比赛即可得出剩下的3匹最快的马。

1. A2 B1 C1 D1

假设胜出的是B1 C1 D1，那么最终最快的马是A1 B1 C1 D1。

总结

一共需要5轮，共计25 + 8 + 4 + 1 + 1 = 39场比赛。我也不知道答案是否正确，是否会存在漏洞，而且是否是最优解，期待大神的解答，感谢！