讨论一个算法，GOOGLE的一个面试题

最好情况下7轮，最坏情况下10轮

几天没来这题还在讨论啊！我想问一下，假如在面试的时候，我们是该答7轮，还是10轮呢，还是两者都要答呢？题目中的“至少”到底是什么意思啊？

巫师已经给出通解的ref了。真要研究算法，研究一下m匹马，n个跑道，前k名的时间复杂度最低的算法，还有点意思。

至少，就是 保证一定可以得出前五名，而场数要最少。

而这个题我觉得 8 场是一定可以得出前五名的，

七场不一定可以得出来。所以它不是至少要的场数。不知道理解得对不对。

不是这样地，因为选的马都是随机的，第六场最快的A组中的马也有可能比最慢的E队中的马慢.

10轮 先五场 取出每场的第一名
这5匹马赛一场 确定1-5，取出第一名a
然后拿a队第二名跟剩下的4名组成一队比赛，取出第一名b
然后拿b所在队紧挨b的后一名跟上面的4匹马比赛，取出第一名c，
然后拿c所在队紧挨c的后一名跟上面的4匹马比赛，取出第一名d，
然后拿d所在队紧挨d的后一名跟上面的4匹马比赛，取出第一名e，
ok 5匹最快的马出来了

马是稳定的，第六场最快是五匹各队第一的马比，所以第六场最快快的马肯定是所有马中最快的啦，又怎么会比E队中的马慢呢？ 第六场可以得出第一名，第七场肯定可以得出第二名和第三名。第八场肯定可以得出第四名和第五名，所以8场够了。我在前面分析过原因。



10轮 太多，关键在于“a队第二名跟剩下的4名组成一队比赛，取出第一名b”，因为马是稳定的，“剩下的4名”再比没有多大的意义，结果基本上等于“a队第二名跟剩下的4名中最快的比取快一点的”两赛道够了，我们应该利用第七场还有三道得出更多的信息才能更快得出结论。不知道这样是不是会更好呢？

前5轮应该没有什么争议，就是5个队都比一场，暂且这样排名，名字在前面的快些。
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 B5
C组 C1 C2 C3 C4 C5
D组 D1 D2 D3 D4 D5
E组 E1 E2 E3 E4 E5

第6轮目前比较统一的做法是让 每个组的第一，即A1,B1,C1,D1, E1比一场，假设 A1>B1>C1>D1>E1 那么这个时候可以淘汰一些马了，淘汰的用--表示，如下:
A组 A1 A2 A3 A4 A5
B组 B1 B2 B3 B4 --
C组 C1 C2 C3 -- --
D组 D1 D2 -- -- --
E组 E1 -- -- -- --

第7轮 A5 vs B1 假设A5>B1 则结束比赛 A1>A2>A3>A4>A4
 
题目都说了，最少！，那么当然我们向最好的方面假设啦！

讨论那么多...我觉得最少7轮,最多8轮

所谓最少7轮,就是数据顺序凑巧,到第七轮的时候就ok了
任何数据顺序,到第8轮都可以出结果

当然,以上的最多最少都是足够"科学"的比较方法上而言,如果愿意,设计一个至少50轮出结果的方法也是可能的

至少8场！
多种情况都可以演算。
本人用最笨的反推法。