25匹马，5个跑道,每个跑道最多能有1匹马进行比赛，最少比多_

NSDaBen

(1)求前3名要7次；

将马分成A、B、C、D、E五组。
第1-5次比赛：各组分别进行比赛，决出各组名次,取每组前三名
A1、A2、A3，
B1、B2、B3，
C1、C2、C3，

D1、D2、D3，

E1、E2、E3。
第6次比赛：A1、B1、C1、D1、E1，

假设得到的结果是A1、B1、C1、D1、E1，A1是跑的最快的，那么分析A组A2、A3还有希望冲进前3，B组呢？只有B2还有希望冲进前3，C组的C1，C2并没有希望冲进前3了，因为C1是比赛的名次是第3名了，D组E组都没有希望了。现在已经知道A1肯定是第一名，剩下A2、A3、B1、B2、C1是有希望冲进前三的。

第7次比赛：A2、A3、B1、B2、C1比赛求出第2，第3即可。

(2)求前5名：

将马分成A、B、C、D、E五组。
第1-5次比赛：各组分别进行比赛，决出各组名次
A1、A2、A3、A4、A5，
B1、B2、B3、B4、B5，
。。。。
。。。。。。E4、E5。
第6次比赛：A1、B1、C1、D1、E1，
第一名是跑的最快的。
第7次比赛：将上次第一名所在组的下一号马再和剩余的4匹1号马比赛，
第一名是跑的第二快的马，由于只有4个名额，所以跑的最慢的马和所在组剩余的马全部被淘汰。
第8次比赛：将上次第一名所在组的下一号马、上次第二名所在组的下一号马和剩余的3匹马比赛，
第一名是跑的第三快的马，由于只有3个名额，所以跑的最慢的两匹马和所在组剩余的马全部被淘汰。
在剩下的比赛中分别淘汰慢的，将排名稍后的加进来比赛，最多跑到第10次就可以选出最快的5匹马。如果在某一次比赛中排名前几的是同一组的且和已经选出的马加一起大于等于5，就可以提前决出前5名。
所以8-10次就可以选出最快的5匹马。

发表于 2015-05-19 11:10:38 回复(11)

沐诩

为什么我看得题目意思和大家的不一样呢？25匹马，5个跑道，每个最多可以跑5匹，那不是刚好一场比赛就能决定出所有排名么。。。

这个题目应该是说25匹马，5个跑道，而且一次比赛最多5匹马，并且只能记录每场比赛的名次，这样，问最少进行多少次比赛，决定前三和前五。

这个问题的关键点在哪里呢？是在于每场比赛只能记录名次而不是所有马的时间，要是像百米赛跑有时间记录的话，那就不用跑了，五场比赛就出结果了！！！

》》》如何得出前三
这也就是说，开始随机分五组，进行小组赛，得出每场第一名A1 B1 C1 D1 E1，
再进行第六场比赛赛，假设该场赛后名次就是A1 B1 C1 D1 E1,
得出第一名后，还有两个名额，就是得出二三名哈，
那一开始和A1小组赛的第二名A2和第三名A3是可以参与到后面比赛角逐下面的排名的，因为快马所在的组，被淘汰的也是可能比其他组晋级的第一名快的，同理 B1比C1快，那B2也是可以进行后面比赛的，而D1和E1是没有资格进行第二三名的角逐了（因为B1,C1就比他们快了），
于是接下来第七场比赛，就是A2 A3 B1 B2 C1，取前两名这样就得出前三。

》》》如何得出前五
前六场和前面一样，假设仍是A1第一名,其余名次依然是B1 C1 D1 E1但是因为是为了得前五，所以后面还有四个名额，所以，这一次D1和E1可以保留继续参赛，而且还要加入A1组剩下A2 A3 A4 A5的全部可以加入，B1组剩下的B2 B3 B4都可加入，C1组剩下的 C2 C3 也可以加入，D1组剩下的D2，E1组剩下的就不能参赛了，当然E1肯定还可以参加的。
于是接下来还要比赛的马匹有A2 A3 A4 A5 B1 B2 B3 B4 C1 C2 C3 D1 D2 E1
因为是最少多少场比赛，竟然是最少，那将A2 A3 A4 A5 B1分一组，如果比赛之后B1排最末，那A2 A3 A4 A5直接就是前四了，那只要七场便得也出了前五的名次。
，其他我就不想考虑的。。。。智商有限啊。我对自己的智商也是醉了。

编辑于 2015-10-23 18:15:56 回复(2)

yxliuxinglin

找出前5名至少需要8次：

将马分成A、B、C、D、E五组。
第1-5次比赛：各组分别进行比赛，决出各组名次
A1、 A 2、 A 3、 A 4、 A 5
B1、B2、B3、B4、B5

C1、 C 2、 C 3、 C 4、 C 5

D1、D 2、D 3、D 4、D 5
E1、E 2、E 3、E 4、E 5
第6次比赛：找出第一名，比较A1、B1、C1、D1、E1 ，假设是A1最快
第7次比赛：找出第二名和第三名，比较 A2、A3、B1、B2、C1，假设A2和A3最快

第8次比赛：找出第四名和第五名，比较A4、A5、B1、B2、C1，前两名分别是第四和第五名

（题目问得是最少需要比较几次，如果在第7次比赛中的第二名和第三名不是A2和A3，那么8次比较是找不出前五名的，需要继续分析。）

发表于 2015-08-22 21:56:41 回复(2)

因为吃素所以菜

7轮比赛

1. 由于一开始对25匹马没有任何信息，而且没有秒表只能靠相对排名信息来分析。所以只能先5个一组的进行5场比赛（因为只有五个赛道），每场比赛都会产生一个小组第一名，同时这个时候我们也了解了每个小组每匹马的排名。

2. 我们把这五个小组产生的第一名作为一组（不如就叫种子组）进行一次比赛。这次角逐出来的第一名一定就是全局的第一名，这个时候前三名的一个已经出来了（第一名就拿出来不用管了）剩下的就是要想办法找到二三名。

3. 确定二三名难就难在有三种情况必须被考虑，（以下名次都是说的全局排名）第一种情况是第二三名同时在小组里被第一名压制，第二种情况是第三名被第二名压制，还有一种情况是都没有被相互压制。最后一种情况我们知道下一场比赛一定要把种子组里的二三名放进去，这个时候还有三个赛道，我们看第一种情况，由于第二三名可能在小组赛的时候被第一名压制，所以我们要把全局第一所在组的二三名加入比赛。这个时候还剩一个赛道，我们看第二种情况。第二种情况是仅第三名被第二名压制，说明我们还需要加入种子组第二名所在的小组的第二名到比赛中，正好五条赛道。这场比赛以后前两名就是全局的第二第三名。这样一来所有的名次都出来了，不需要更多比赛了，总共5 + 1 + 1 = 7 场比赛。

发表于 2021-05-25 22:18:51 回复(0)

Medill1

找出前五名，应该是7-10次。

前六次都是一样的，假设第六次的结果是A1 > B1 > C1 > D1 > E1。

那么除了A1，有可能是前五名的侯选池是A2-A5，B1-B4，C1-C3，D1-D2，E1。

第七次可以不妨取A2，A3，A4，A5，B1。这种方法优先考虑A组的马，当然也可以优先考虑其他组。不过不论怎么选，比较的五匹马需要符合两个规则：

1 如果包含了排名靠后的组，那么靠前的组在候选池中的头名一定要被比较（比方要考虑E1，那么A2，B1，C1，D1必须被包括进行比较）。这保证了每一次比较都能选出侯选池中最快的马。

2 比较中至少要有一个小组头名。

这样的话，第七次一定会选出速度第二的马。实际上，B2的排名决定了至多还需要比较几次。极端情况是A2>A3>A4>A5>B1。就能得到前五名的马。

第八次按最坏情况考虑，B1>A2>A3>A4>A5。有可能是前五名的侯选池是A2-A4，B2-B4，C1-C3，D1-D2，E1。可以选A2，A3，A4，B2，C1（这里一定要有C1，比较中至少要有一个小组头名）。

第八次一定会选出速度第三的马。

以此类推，最多第十次一定会选出速度前五的马。

发表于 2017-08-29 15:55:47 回复(0)

Tommyzt

1、前三名需要7次比赛

首先分5组，进行五次组内比赛选出各组前三名，第六次比赛是各组第一名进行比赛，选出第一名。

然后，将A组第二第三，B组第二第三，C组第二进行比赛，选出前两名。

共进行7场比赛。

2、前五名思路类似，分组比赛再分组再比赛，至少8次可以得出结果

发表于 2015-08-05 09:28:10 回复(0)

noble4cc

找出前三名：

25匹马，分成ABCDE五个组，这五个组分别比赛，然后选出各个组的第一名进行比赛，得出第一名，假设是A1然后，淘汰第六次比赛的后两名所在的组，假设为DE组，因为我们DE两个组已经不可能进入前三名了，所以要淘汰，然后选出剩下的三组，ABC三组，然后让AB组中的第一二名，C组中的第一名进行比赛，得出前两名，选出的这三匹马就是这个25匹马中的前三名。所以一共需要7次

找出前五名：

找出前五名也类似，分组，分别比赛。然后找出第一名，然后选出第二名，现在只剩三个名额，所以要淘汰一个组，而后选出第三名，淘汰一个组，剩余两个名额，然后将这次比赛中第一名个第二名所在的组选出前两名，第三名所在的组选出前一名进行比赛，淘汰一个组，最后在进行一次比赛，一共进行10次

发表于 2015-05-20 18:07:04 回复(0)

陈木木

找出前3名最少需要7场就可以确定。首先我们将25匹马分成5组，分别为ABCDE，5组分别进行比赛决出各小组名次；接着让各小组第一进行比赛决出冠军，我们假设各小组第一分别是A1, B1, C1, D1, E1，并且速度A1 > B1 > C1 > D1 > E1；接着2，3名可以在一场比赛内决出，分别由A2, A3, B1, B2, C1参赛；这样总共进行了5 + 1 + 1 = 7场；找出前5名的思路和这个类似。

编辑于 2015-05-18 13:06:11 回复(1)

牛客860948号

http://hxraid.iteye.com/blog/662643

发表于 2016-07-19 09:21:15 回复(0)

中二病晚期

的确是7次就能决定前三名.

首先我们假设25匹马分别标号成5组,每组5匹马,即

A1,A2,A3,A4,A5

B1,B2,B3,B4,B5

C1,C2,C3,C4,C5

D1,D2,D3,D4,D5

E1,BE2,E3,E4,E5

-------------------------------------------------------------------------

第一步,

每组进行一波赛跑,我们可以得到每组的第一名

(比赛后是能够知道每组第一名具体是哪一匹马的, 这里假设每组的1号,方便说明)

假设每组第一名为A1,B1,C1,D1,E1

-------------------------------------------------------------------------

第二步,

每组第一名为A1,B1,C1,D1,E1进行一次比赛

我们能够得到前三名, 为了方便说明我们就假设前三名是A1,B1,C1

这个时候我们可以知道,这一步的比赛中取得第四和第五 D,E两组的马都是与全部马匹前三名无缘的.

假设

A1是第一名

B1是第二名

C1是第三名

那么我们需要考虑到A组中原来被淘汰的A2和A3是不是可能比B1或者C1快

同时考虑B组中的B1是不是可能比C1快.

即如果各组第一名进行比赛得到的前三名是 A1 > B1 > C1

存在以下几种情况:

A1 > B1 > C1 (C1比A2快)

A1 > A2 > B1 (A2比B1快,但是运气不好匹配到最强王者A1提前歇菜了)

A1 > A2 > A3 (么得话说,A组是真的强)

A1 > B1 > A2 (A2比C1快)

A1 > B1 > B2 (C1是真的没***)

总结:A2,A3,B1,B2,C1这五匹马都在竞争第二名和第三名,其他的马都没有希望

-------------------------------------------------------------------------

第三步,

让A2,A3,B1,B2,C1这五匹马进行最后的比赛,得出第二名和第三名.

-------------------------------------------------------------------------

总结:如果要决定前三名.第一步5次,第二步1次,第三步1次,一共进行7次比赛

看到有些同学对第三步为什么进行1次就能决定最后的名次感到疑惑,所以在这里对第二步的情况进行了详细的分析,希望能帮到大家.😊

发表于 2019-03-26 20:24:36 回复(0)

牛客220598544号

前一问题：第六轮
A1
B1
C1
D1
E1

前二问题：在六轮基础上，第七轮
-A1、A2
B1、B2

前三问题：在六轮基础上，第七轮
-A1、A2 、A3
B1、B2
C1

前四问题：因为竞位马匹较多，无法直接建立在第六轮进行一轮概括，所以在第七轮基础上，开始第八轮
-A1、-A2 、A3
-B1、B2
C1
或者
-A1、A2
-B1、B2
-C1、C2
D1
前五问题：因为竞位马匹较多，无法直接建立在第七轮进行一轮概括，所以在第八轮基础上，开始第九轮
-A1、A2
-B1、B2
-C1、C2
-D1、D2
E1

或者

-A1、-A2 、-A3、-A4、A5
B1
C1
D1
E1

-A1、-A2 、-A3、A4
-B1、B2
C1

-A1、-A2 、A4
-B1、B2
-C1、C2
D1

>>
>> 副号(-)表示已经被前面轮选定的结果
所以九轮妥妥的可以。

发表于 2021-03-03 21:57:13 回复(0)

司马老头

跑5次，25名的各名次都能得出了（记录时间成绩）

发表于 2020-11-21 19:23:55 回复(0)

牛客259756516号

求前5名最少要7次；

将马分成A、B、C、D、E五组。
第1-5次比赛：各组分别进行比赛，决出各组名次,取每组前五名
A1、A2、A3、A4、A5，
B1、B2、B3、B4、B5，
。。。。
。。。。。。E4、E5。

第6次比赛：A1、B1、C1、D1、E1。

A1、A2、A3、A4、A5

B1、B2、B3、B4
C1、C2、C3

D1、D2
E1

第7次比赛:我们将B1和A2、A3、A4、A5比赛，相当于将B1插入

如果B1是第五名，则前5名必然是A1、A2、A3、A4、A5,总共7次。

如果B1是第四名，相当于插入到A5，则前5名必然是A1、A2、A3、A4、B1,总共7次。

如果B1是第三名，相当于插入到A4，则还剩下第五名的名额，则只需要A4、B2、C1比赛，总计8次。

如果B1是第二名，相当于插入到A3，则还剩下第四、五名的名额，

则只需要A3、A4、B2、B3、C1、C2、D1比赛，

第8次比赛随机选5个比赛选取前两名，（当然这里也可能有极端情况）

上次前两名和剩下的两个再比较。

总计9次。

如果B1是第一名，相当于插入到A2，

则还剩下第三、四、五名的名额，

则只需要A2、A3、A4、B2、B3、B4、C1、C2、D1、D2、E1比赛，

第8，9次比赛选10个分成两组比赛两次，选取前三名，

第10，11次比赛，8,9次的前三名和剩余的一名比赛2次，

总计11次。

所以最少在7~11次之间。

发表于 2020-09-17 00:22:26 回复(0)

快乐肥宅B

这种题总是BUG一大把，你要是单纯就分五组，正好把前五名分到一组了，那这组你是淘汰还不不淘汰？你淘汰就得不出正确结果，不淘汰就设计不出来淘汰规则，除非你重复对比。

发表于 2020-07-20 04:46:38 回复(1)

牛客853954293号

找出前3名最少需要7场就可以确定，不多说。找出前5名最少需要9场就可以在任何情况下确定。首先我们将25匹马马分成5组，分别为ABCDE,5组分别进行比赛决出各小组名次;接着让各小组第一进行比赛决出冠军，我们假设各小组第一分别A1,B1,C1,D1,E1,并且速度A1>B1>C1>D1>E1。所以，第一名为A1。接着2,3名可以在一场比赛内决出，分别由A2,A3,B1,B2,C1参赛: ①假设A2,A3分别为2,3名，B2在这组中跑最慢。这样第4,5名在A4,A5,B1,C1中选出。确定第4,5名需要1场。 ②假设A2,A3分别为2,3名，C1在这组中跑最慢。这样第4,5名在A4,A5,B1,B2中选出。确定第4,5名需要1场。 ③假设A2,B1为2,3名(无论先后)，A3在这组中跑最慢。这样第4,5名在B2,B3,C1,C2,D1中选出。确定第4,5名需要1场。 ④假设A2,B1为2,3名(无论先后)，B2在这组中跑最慢。这样第4,5名在A3,A4,C1,C2,D1中选出。确定第4,5名需要1场。 ⑤假设A2,B1为2,3名(无论先后），C1在这组中跑最慢。这样第4,5名在A3,A4,B2,B3中选出。确定第4,5名需要1场。 ⑥假设B1,B2分别为2,3名，A3在这组中跑最慢。这样第4,5名在A2,B3,B4,C1,C2,D1中选出。这里选第4,5名，如果A2>C1（在选2,3名可以知道），只需在A2,B3,B4,C1中第4,5名，只需要1场。如果C1>A2，就需要在A2,B3,B4,C1,C2,D1中选第4,5名，至少要2场。确定第4,5名需要2场。 ⑦假设B1,B2分别为2,3名，C1在这组中跑最慢。这样第4,5名在A2,A3,B2,B3中选出。确定第4,5名需要1场。 ⑧假设B1,C1分别为2,3名，A3在这组中跑最慢。这样第4,5名在A2,B2,B3,C2,C3,D1,D2,E1中选出。确定第4,5名需要2场。 ⑨假设B1,C1分别为2,3名，B2在这组中跑最慢。这样第4,5名在A2,A3,C2,C3,D1,D2,E1中选出。确定第4,5名需要2场。一共5+1+1+2=9场。

编辑于 2020-06-15 21:53:10 回复(0)