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

我怎么觉得是8场，，前面的你说的是对的。
前面5场，所有的马跑一次。得到每场最快的马（第一梯队）和第二快的马（第二梯队）。
第6场，最快的5匹马（第一梯队）跑一次。标记为a,b,c,d,e
第7场，第二快的马(第二梯队）跑一次。得到的其中最快的马，标记为f。f就第二梯队里最快的了。
第8场，不用a在参加了，因为a就是最快的马了。让b,c,d,e,f跑一次，淘汰最后的一名。然后把a在加到里面，得到的就是最快的了。

有没问题？

楼上的当然有问题，我觉得还是10场

最多9场
前面5场就不说了
第2，3明只需比一场就可以决出，其他的每选出一名都需要比一场

特殊情况下，运气好的话，7场，8场都有可能

我觉得应该是29场

每六场能决定一匹马

最后一次是五场

6+6+6+6+5=29

第二个是不是（N/M+1）*Y-1

这里需要搞清楚一个事 25匹马分成A B C D E 5个组
前面5场决出 每组 第一

第6场让每组第一名决出高下

假设A组的的第一最快 D组第一最慢
但是能保证A组第二（该组第一和第二差距很大）就一定比D组（该组第一和第二差距很小）第二快吗？？？（而第6场差距也很微弱）

更极端的是某个组的5匹马就是跑的最快的那5匹。。。

先把马分成5组，每组5匹

第1场到第5场分别决出每组第一
第6场对每组的第一名进行比赛
根据结果，假定第六场的5匹马是
a1 > b1 > c1 > d1 > e1
a1所在的组的5匹马是a1 > a2 > a3 > a4 > a5
b1所在的组的5匹马是b1 > b2 > b3 > b4 > b5
c1所在的组的5匹马是c1 > c2 > c3 > c4 > c5
d1所在的组的5匹马是d1 > d2 > d3 > d4 > d5
e1所在的组的5匹马是e1 > e2 > e3 > e4 > e5

显然a1是第1名

第7场，将a1剔除出去，把a2换进来，与b1,c1,d1,e1进行比赛
因为比赛仍然是在每组最快的马之间进行的（a1已经排除在外了）
这场比赛的胜者就是除了a1之外最快的马，即第2名

第8场，先将第7场胜者（第2名）剔除出去
将第7场胜者所在组的下一匹马与参与第7场比赛的剩下4匹马进行比赛
显然比赛仍然是在每组最快的马之间进行的
所以，这场比赛的胜者就是第3名

依次下去，到了第10场比赛就可以决出第5名了

以上说明的是，最少要10场就一定能决出前5名
至于这个10是不是最小值，我无法证明

恩 根据我的想法（就是某组第一剔除了，后面补上） 就是10场能决出最快的5匹马（绝对保证正确）
但是就是不知道是不是最小值了

ls的，现在是选前5最快的。
如果D组第一是第一梯队最慢的（第5），那D组从第2名以后怎么也不可能挤入前5了；


注意题目，是问至少：
答案是7场，下面是我的表述：

前5场的比赛以后取每组第一进行比赛（第6场），排名如下所示：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    u
c    g    l    q    v
d    h    m    r    w
e    i    n    s    x

在第6场中排名第5的那组，从第2名以下 无法进入前5，同理可知，第4名那一组自第3名以下无法进入前5.。。。。，如下：

1    2    3    4    5

a    e    j    o    t
b    f    k    p    X
c    g    l    X    X
d    h    X    X    X
e    X    X    X    X

第7场，取第6场的第5名与  第6场的前4名所在的组的第2名进行比赛，如果这些第2名都比第6场第5名慢，那么第6场第5名就是前5的最后一个，前5名就诞生了。 (题目的至少到这里就得到了解答。

如果不满足这种情况，则淘汰比第6场第5名还慢的那组自第2名开始的所有马，剩下的情况就比较简单了，看着也知道10场绝对能得到最快的5匹。

我觉得你的是对的，我前面也说过这样排除那些不需要比赛的，但是得出的结果是八场。但是这道题目说的是至少，所以如果能找到一种比赛组合可能七场就能确定的话，那应该就是七场了。我没有抓住题目的要旨，即“至少”。就好比一个排序算法一样，拿插入排序为例，如果问插入排序至少要比较多少次才能确定它是有序的，答案是n，当所有的数据本来都是顺序排列的时候；当问至多要比多少才能确定呢，答案是(n-1)n/2次，即所有的数据都是逆序的。