赛道快马问题
今天遇到一个比较有趣的面试题
25匹马，5个赛道，选出最快的三匹马（无计时器，每个赛道仅能容一匹马通行）
思路是这样的：
1、25匹马，分为 A-E 五组，进行5场比试
2、将每场最快的马列出来，分别冠以 A1、B1、C1、D1、E1，剩下的按照次序进行分列：即第二名组 A2、B2、C2...，第五名组 A5、B5、C5... E5
3、将2中决策出来的最快的5匹马，A1-E1 进行1场比试，则最快的马已经决策出来，假设是A1
4、接下来选择第二名和第三名，若 A1-E1 按照速度最快的进行排序，即 A1 快于 B1，B1 快于 C1，C1 快于 D1，D1 快于 E1，即对于 A-E 组，所有的 Ax > Bx > Cx > Dx > Ex
5、有这样一种情况，无法得知 A 组的第二名 A2 是否跑的比 B 组的第一名 B1 还要快（刚好，假设 A 组存在这5匹马都远快于其他组，虽然 A2 位于第二名组，但是比第一名组中的 B1 还要快），因此需要选择 A2，B1决策第二名
6、同样的道理，选择第三名时，无法得知，A3 是否快于 B1，或 B2 是否快于C1，因此第三名决策可以将 A3、B2、C1
7、结合 6&7，可以用一场比试决策出第二和第三名。
因此仅需要 5 + 1 + 1 = 7 即可决策出前三名。
拓展一下思路，如果是前五名呢？
1、25匹马，分为 A-E 五组，进行5场比试
2、将每场最快的马列出来，分别冠以 A1、B1、C1、D1、E1，剩下的按照次序进行分列：即第二名组 A2、B2、C2...，第五名组 A5、B5、C5... E5
3、将2中决策出来的最快的5匹马，A1-E1 进行1场比试，则最快的马已经决策出来，假设是A1
4、接下来选择第二名和第三名，若 A1-E1 按照速度最快的进行排序，即 A1 快于 B1，B1 快于 C1，C1 快于 D1，D1 快于 E1，即对于 A-E 组，所有的 Ax > Bx > Cx > Dx > Ex
到此刻，我们决策出，最快的马 A1，并且知道 所有的 Ax > Bx > Cx > Dx > Ex
那么求前五名，剩下四名，应该怎么选呢
假设：
选 A2、A3、B1、B2、C1 按照选取前三名的方式选择
可以决策出前三名，有以下几种情况
A2、A3，分别为第二第三，则可以确定，第四名B1（确定），第五名在B2/C1中（确定）
A2、B1，分别为第二第三，则可以确定，第四名 A3/B2/C1，第五名的概率...
B1、A2，分别为第二第三，第四名 A3/B2/C1，第五名的概率...
B1、B2，分别为第二第三，第四名在 A2/B3/C1，第五名的概率...
B1、C1，分别为第二第三，第四名在 A2/B2/C2/D1
因此，此种方式，也不可选
a. 考虑 A2、A3、A4、A5、B1 进行比拼
此举最少决策出第2名（A2/B1），第三名 A3/A4/A5/B1
b. 从 A2、A3、A4、B2、C1 进行比拼
此举最少决策出第3名（A2/B2/C1）
...罗列不出来了。使用新方法
1、首先5场，必须分5组，A1-A5，B1-B5，... E1-E5
2、选第一名，需要 A1/B1/C1/D1/E1，A1最快决策出来
3、选第二名，此时我们知道目前最快的两匹马是 A2/B1
4、在A2为第二名的前提下，第三名可能是 A3/B1
在B1为第二名的前提下，第三名可能是 A2/B2/C1
也就是说，第七次决策，可以稳定出前三：需要 A2/A3/B1/B2/C1，照着这个思路
5、A2为第二名，A3为第三名，第四名可能是 A4/B1
A2为第二名，B1为第三名，第四名可能是 A3/B2/C1
B1为第二名，A2为第三名，第四名可能是 A3/B2/C1
B1为第二名，B2为第三名，第四名可能是 A2/B3/C1
B1为第二名，C1为第三名，第四名可能是 A2/C2/D1
综合看，第八次决策，A2为第二名情况下，新增 A4；B1为第二名的情况下，新增B3、D1
6、那么去除第七次决策必出的A2,B1后，求第四第五。在A3/B2/C1/A4/B3/D1六匹马中决策，最少需要2次。
因此共计 5 + 1 + 1 + 1 + 2 = 10