[360笔试题]赛马

这是一道360的在线笔试题:

赛马,有25匹马,每次只能5匹马进行比赛,比赛只能得到5匹马之间的快慢程度,而不是速度,请问,最少要比多少次,才能获得最快的前3匹马?

解答:这道题乍一看,第一感觉就是肯定要分组,5个一组分成5组,然后比赛,得到每组的组冠军。然后让5个组冠军比赛得到前三名,似乎这样就可以了,这也是我的第一反应。

但是这是一套错误的方案,有可能有这样的分组,那就是第一组的5匹马是实力最强的,这种情况就得到不前三名。于是还要加赛一场,注意只取前三名。

最终答案要经过三步:

1.把25匹马分成5组,每组5匹马,这样经过五场比赛得到每组的组冠军。
2.进行第六场比赛,让前面得到的每组的组冠军比一次。淘汰最后两名,同时也淘汰了最后两名所在的组,他们组的任何马都不可能进入前三了
3.进行第七场比赛,到目前为止,可以确定的是第六场的冠军就是全部马的第一名,所以还需要选剩下的两个名额。剩下的另个名额的候选对象是:
冠军组的第二、第三名(正好牛逼的马都分到了这一组)
亚军组的第一、第二名(冠军组的二三名不厉害,但是亚军组的第二名也很厉害)
季军组的第一名(因为它前面有一个亚军,所以如果前三来自季军组,一定是它)
所以最后的一场,也就是第七场的比赛对象是:冠军组的第二三名,亚军组的第一二名,季军组的第一名。从这场比赛中选出两匹马。
最后加上第六场的冠军,就得到了所有马的前三名。

  

原文地址:https://www.cnblogs.com/stemon/p/4713891.html