2015美团网【软件研发】笔试真题

题意如下：25匹马，每次最多5匹马比赛，问多少次能找出前三名的马。

当时答的是10次，汗颜，走出考场就发现答的不对了，现分析如下：

1、首先赛跑5次，找出每次跑的前三名。记为1i，2i，3i，i从1新-5。

2、将1i共5匹马一组进行赛跑，此时找出第一快的马。将第四快和第五快的马直接抛弃。

3、此时还剩3匹马，这个时候第二名和第三名只可能从步骤2当中剩余的两匹马和2当中跑得最快那匹马之后的两匹还有跑得第二快的之后的那匹。

4、将步骤3中的五匹马再次赛跑一次，决胜出第一名和第二名。和步骤2中的那匹一起成为前三快的马。

图示如下：

a1-a5

b1-b5

c1-c5

d1-d5

e1-e5

跑完5轮，假设只剩:

a1-a3

b1-b3

c1-c3

d1-d3

e1-e3

这个时候取出：a1,b1,c1,d1,e1进行赛跑。

假设a1跑得最快，b1第二快，c1第三快。

这个时候只可能出现：a2,a3,b2,b1,c1争夺2,3快的马。想想为什么？

假设是b3争夺，则b3 < b2 　b3　< b1   b3  < a1 此时必然不是前三快。同理c2,c3都是。更不用提di 和 ei 了。

所以一共七轮足矣决出最快三匹马。

-----正文分割线-----

（原文真题来自应届生）