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

正解啊

六次就ok了

晕，啥时代了？连个计时器都没有啊？

1－5轮：分成5组分别比赛。（不是最好，但最简化）
6轮   ：每组的第2名比赛。从快到慢（从小到大）依次命名为a2,b2,c2,d2,e2。按照这个规则给所有的马命名。
        此时a1肯定入围，其余争夺前4。将a1排出讨论。
        b4比a2,b1,b2,b3都大，所以不可能入围。
        c2比b1,c1,a2,b2都大，也不可能入围。
        所以只有剩下的a2,a3,a4,a5,b1,b2,b3,c1,d1,e1争夺前4。其中a2<a3<a4<a5，b1<b2<b3， a2<b2

7轮   ：将a3,b2,c1,d1,e1比赛。此次比赛的第一名直接入围，剩下的角逐前3。因为c1,d1,e1的等价性，不妨根据比赛结果设c1<d1<e1。然后分情况讨论：

       引论甲：如果b3要入围，那么入围人选只能是a1,b1,a2,b2,b3。所以这场比赛b2,a2分别占据前二才行。
       
       如果a3排第一。那么a2,a3直接入围。此次比赛的第二名，第三名和b1,a4,a5决出最后2名入围者。总共是8。
       如果a3排第二，c1第一。比a3快的只可能c1,a2,b1，所以a2,a3直接入围。剩下的a4,a5,b1和这轮第三名，第四名争夺最后一名入围者。总共8轮。如果a3排第二,b2第一。b1,b2,a2直接入围。最后一个名额由a3,b3和刚才第三名争夺产生。总共8轮。
       如果a3排第三。那么刚才比赛最后2名直接失去比赛资格。可能比a2小的只有前2名和b1，所以a2直接入围。再加上前两名直接入围。第6轮结束剩下的10名选手中，3名入围，2名失去资格，剩下的5名选手刚好可以一场比赛决出最后一个名额。总共8轮。
       如果a3排第四。a3，a4,a5都失去资格。根据引论甲，b3也失去资格。只剩下有a2,b1和刚才的前三名，5人只需要一场比赛即可。总计8轮。
      如果a3第五。a3,a4,a5失去资格。根据引论甲，b3失去资格。比赛前2名直接入围。剩下的4人再进行一场比赛即可。总计8轮。


   所以按照这种算法，最多8轮就可以决出前5名。


   

       

       

复杂的问题，挺不容易，所谓的正解，有些牵强

给一个比赛的办法：

1) 1-5轮，分成5组分别比赛，按照比赛结果从快到慢排成5组

2) 从5组中抽出最快进行比赛，把最快的放到一边去，它肯定是第一，是前5名之内的；最慢的所对应的那一组的余下4匹被淘汰，因为比它快的就有5个，肯定是在前5名之外。把余下的4匹按照从快到慢的顺序马排成一组，进入被淘汰的那一组的位置。

3) 重复上面的方法4次，得到5匹最快的马。

10场是正确的。一匹马只要在横向和竖向都排第一，一定是这个矩阵中最快的，被选出来。

[有N匹马，有M个赛道，试问要至少多少场比赛才能知道跑得最快的Y匹马。]

A1 A2 A3 A4 A5
B1 B2 B3 B4 B5
C1 C2 C3 C4 C5
D1 D2 D3 D4 D5
E1 E2 E3 E4 E5

int c1 = N % M ==0 ? N / M : N / M + 1; //经过c1轮比赛得到一个矩阵.
int count = c1 + Y; //再经过Y次比赛找到最快的. 每次从最左竖列开始，选中一个后其所在横列顺序补上.
需要count次。(最多也就需要count次就可以了.)

我也觉得需要10场

应该9场就可以出来
前5场：
A1>A2>A3>A4>A5
B1>B2>B3>B4>B5
C1>C2>C3>C4>C5
D1>D2>D3>D4>D5
E1>E2>E3>E4>E5
第6场：A3>B3>C3>D3>E3,剩下
A1>A2>A3>A4>A5
B1>B2
C1>C2
D1>D2
E1>E2
第7场：A3,B1,C1,D1,E1比较，有下面几个结果：
1）A3>B1>C1>D1>E1，结果为
A1>A2>A3>A4>A5
B1>B2
C1
此时再比一场即共8场结果就出来了。
2）B1>A3>C1>D1>E1，结果也为
A1>A2>A3>A4>A5
B1>B2
C1
3）B1>C1>A3>D1>E1，结果为
A1>A2>A3
B1>B2
C1>C2
再比一场也出来了
4）B1>C1>D1>A3>E1，结果为
A1>A2
B1>B2
C1>C2
D1>D2
也是再比一场出结果
5）B1>C1>D1>E1>A3，结果为
A1>A2
B1>B2
C1>C2
D1>D2
E1>E2
此时需再比两场即共9场才能出结果

这里的同志哥大多都把cs专业学没了。