跑马问题--36匹马，跑道每次最多只能有6匹马进行比赛，最少进行多少次比赛能比出前3名？

我就是我 2022-12-09 02:40 423阅读 0赞

**目录**

一、36匹马赛跑，跑到同时只能容许6匹马。而且36匹马速度不同，但是每次跑的速度恒定。问跑多少次可以选出第一、第二、第三名？

二、25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？

1、前三名的解题思路

2、前五名的解题思路

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

## 一、36匹马赛跑，跑到同时只能容许6匹马。而且36匹马速度不同，但是每次跑的速度恒定。问跑多少次可以选出第一、第二、第三名？ ##

36匹马赛跑，跑到同时只能容许6匹马。而且36匹马速度不同，但是每次跑的速度恒定。问跑多少次可以选出第一、第二、第三名？

A. 7    B. 8    C. 9    D. 12

可以分三步走。  
（1）第一步，将36匹马分成6组，1次跑一组，跑6次。分别得到每组的排名。  
A1, A2, ..., A6;  
B1, B2, ..., B6;  
C1, C2, ..., C6;  
D1, D2, ..., D6;  
E1, E2, ..., E6;  
F1, F2, ..., F6  
（2）第二步，让每组的第一名在一起跑一遍，取前三名（假设还是A1, B1, C1）  
那么，A1肯定是整体的第一名  
（3）第三步，  
有可能成为整体第二的马为A2, B1  
有可能成为整体第三的马为A3, B2, C1，一共5匹马，让这5匹马一起跑一遍，  
选出前两名，就分别是整体的第二名、第三名  
因此，总共需要6 + 1 + 1 = 8次，答案选B.

## 二、25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？ ##

这道题也有类似的变形：25匹马，5个跑道，每个跑道最多能有1匹马进行比赛，最少比多少次能比出前3名？前5名？

其答案可以参考下面这个人的，总结的比较好。[https://blog.csdn.net/Xu\_JL1997/article/details/89021916][https_blog.csdn.net_Xu_JL1997_article_details_89021916]

在此，我也做下总结。

### 1、前三名的解题思路 ###

将25只马分成五组，每组比赛一次，总共比赛5次。得到每组的排名结果如下（假设每组的排名为A1->A2->A3->A4->A5）。也就是得到5个有序数组。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70][]

将五组的第一名放到一起比赛1次，得到第一名为A1（假设排名为A1->B1->C1->D1->E1），也就是整体的第一名。

此时整体的第二名、第三名的范围就在“从A1出发，长度在3以内的路径中”，如下图所示，也就是A2、A3、B1、B2、B3、C1。将它们放在一起比赛1次，就可以知道整体的第二名、第三名了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1][]

因此，总共需要5+1+1次比赛。

### 2、前五名的解题思路 ###

思路一：

先通过分组得到5个有序数组（5次比赛）。

接下来采取Merge操作（归并操作），将5个指针分别指向5个有序数组的第一个数字（5个分组各自的第一名），将五个指针所指向的放到一起比赛1次，得到当前第一名，同时将第一名的指针向右移动一位。重复刚才的操作5次，不断得到“剩余的马中的第一名”（5次比赛）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2][]

因此，总共需要5+5次。

思路二：参考 [https://blog.csdn.net/Xu\_JL1997/article/details/89021916][https_blog.csdn.net_Xu_JL1997_article_details_89021916]

还是先通过分组得到5个有序数组（5次比赛）

找到五个分组第一名中的整体第一名（1次比赛）

将B1与A2、A3、A4、A5进行一次比赛（1次比赛），根据B1在其中的排名，来决定是否需要对后面4组进行比赛。这是因为，B1是后面4组的最大值，如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 3][]

如果是\[A2, A3, A4, A5, B1\]，则无需再比，第二到第五名分别是A2-A5，总共需要7次比赛；

如果是\[A2, A3, A4, B1, A5\]，无需再比，第二名到第五名分别是A2, A3, A4, B1，总共需要7次比赛；

如果是\[A2, A3, B1, A4, A5\]，此时确定了第二名到第四名（A2, A3, B1），A4不一定是第五名，因此需要对\[A4, B2, C1, D1, E1\]再进行一次比赛，总共需要8次比赛；

如果是\[A2, B1, A3, A4, A5\]，此时确定了第二名、第三名（A2, B1），最差情况下需要进行两次归并操作，也就是再进行2次比赛，因此需要9次比赛；

如果是\[B1, A2, A3, A4, A5\]，此时只能确定第二名为B1，对于第三、第四、第五名，最差情况下需要进行3次归并操作，也就是3次比赛来确定，因此需要10次比赛。

因此，总共需要7到10次比赛。

这种思路有点类似于【剑指offer  二维数组中的查找】，利用元素之间的有序性和相对大小，来缩小搜索范围，起到一个“剪枝”的作用。

[https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_abc3fe2ce8e146608e868a70efebf62e_tpId_13_tqId_11154_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

[https_blog.csdn.net_Xu_JL1997_article_details_89021916]: https://blog.csdn.net/Xu_JL1997/article/details/89021916?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70]: /images/20221123/3dab28caf77441c3b9ae3976aa6e9464.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 1]: /images/20221123/219209a54a694f97a2c249927af36fcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 2]: /images/20221123/6ea2efee81a640dd91bdc331e7eb0721.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzMwOTczNDMx_size_16_color_FFFFFF_t_70 3]: /images/20221123/e8290893112e478cb243b9dae25ea0dd.png
[https_www.nowcoder.com_practice_abc3fe2ce8e146608e868a70efebf62e_tpId_13_tqId_11154_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking