腾讯面试题。 985一条街来看看？

八轮 ，每一轮算出马跑的时间比较就行啦

引用 @独立团骑兵连孔连顺 发表的:
可能不是标准答案: 64匹马分8个跑道，取每个跑道前四名，一共取得32匹，然后让每个跑道的第一名赛一场，第一名为所有组最快，然后去掉后四名的赛道的马，这时还剩下第一名赛道2、3、4，第二名赛道1、2、3、，第三名赛道1、2，第四名赛道1，9匹马比两次，次数8+1+1+1=11

11次是一定能得到前4的次数吧。要是只是最少次数的话，我8轮赛完，直接任取一组的第5名和另外7组的第一名加赛一轮，若该第五名跑最快，那该组前4既为最快4匹马，这样最少9轮即可。

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

正解

通俗的解释一下，这个命题的先天条件是没有计时器和马每次跑的用时都是一样的。
先跑8次决出每组第一名；
每组第一名比1次，然后选出前四名，后四名排名的组的32只马全部淘汰，意思就是你们组的老大都进不了前四你还想进前四么？把前四的组分别为ABCD组，A1自然就是王中之王，自然是第一，那么A2A3A4B1B2B3C1C2D1这9匹马都有机会争234名；
选定的这9匹马，选出8匹，跑1次决出前三；
前三和另一匹马跑1次，决出真正的2 3 4。
8+1+1+1，完备最快。

引用 @小黑黑又黑 发表的:
跑8个回合，记录每个时间，直接得到，其实是个脑筋急转弯，专坑沉迷算法的小伙伴

要是记录时间，腾讯还用得着出这种题？你这就是抬杠了
本身就是考逻辑思维，脑筋急转弯，你以为都是小学生吗

引用 @韦我独尊2 发表的:
8次就行了，可以带计时器

他要最快的4匹马 你都说计时器了 我是不是可以说 每组的第一名看到后面的跑不过它没用全力呢

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

你说的最多你就是对的

9次，每个马先跑一次64/8=8 ，计时的时候第一的马再比一次。9次。

引用 @滚去养猪呐 发表的:
如果前八正好就是在同一组呢

所以第一名组拿了1234出来再比

我觉得9次最少，他说的最少不就是最特殊的情况吗，那就是第一组跑一次 把第四名拿出来和其他在跑8次 每次都第一名，不就9次 刚好第一组的前四就是总的前四，最特殊的情况

简单呀，充钱的先跑半圈，死氪金的起点变终点，不充钱的就。。。。

跑四次，可以找个秒表，记一下时间😁

引用 @你好心晴 发表的:
也可能10次， 9匹马留下冠军组的4 如果3被淘汰的话4肯定被淘汰就不用第11次了。所以答案是，11次肯定可以测出来，10次可能测出来

这是最全面的答案。更严谨的说法是：
留下冠军组的第四名，或亚军组的第三名，或季军组的第二名。如果它的前一名被淘汰了，那就不用比第11次了。 如果留下第四名组的那匹，如果第三名那匹被淘汰了，那也不用不第11次了。 [ 此帖被居然还有这种操作在2019-11-04 16:29修改 ]

引用 @你好心晴 发表的:
也可能10次， 9匹马留下冠军组的4 如果3被淘汰的话4肯定被淘汰就不用第11次了。所以答案是，11次肯定可以测出来，10次可能测出来

对头，👍

引用 @mengtuo7 发表的:
奥运会比法，八八分组，小组前四进下一轮，8+4+2+1共计15回合

老哥6啊

引用 @霹雳无敌仲恺小霸王 发表的:
厉害，核心在于不是测速，而是比快慢。如果测速的话，必须全部跑完就清楚

比快慢不也得必须全部跑完吗？

基本上跑10个回合就决出来了

这种题不是考你计算能力吧。是考你分析能力。
我觉得每匹马跑一次就够了。
你把所有的马的成绩计时，完了直接从这里面选出4匹最快的不就完了。

引用 @mengtuo7 发表的:
奥运会比法，八八分组，小组前四进下一轮，8+4+2+1共计15回合

有死亡之组和水货之组咋办

引用 @詹姆斯别克 发表的:
9匹马怎么跑两次

一二三组，八匹跑一次，如果三组第一没进前三，那就不用跑第二轮，10次结束；如果进前三，把这次前三和第四组一号跑一次，11次结束，前三加前面的冠军就是前四的马。

引用 @南苑小先生 发表的:
9次，第一轮的第一名加入下一组，以此类推

应该是第一轮第四名

9次
第一组8匹 选出第一
然后第一直接去下一轮和七匹马跑 选最快的
同理 最快的和下面7匹一起跑
877777777
9轮

引用 @mengtuo7 发表的:
奥运会比法，八八分组，小组前四进下一轮，8+4+2+1共计15回合

这个肯定不是最少的

引用 @独立团骑兵连孔连顺 发表的:
可能不是标准答案: 64匹马分8个跑道，取每个跑道前四名，一共取得32匹，然后让每个跑道的第一名赛一场，第一名为所有组最快，然后去掉后四名的赛道的马，这时还剩下第一名赛道2、3、4，第二名赛道1、2、3、，第三名赛道1、2，第四名赛道1，9匹马比两次，次数8+1+1+1=11

留下第一名赛道的4，或第二名赛道的3，或第三名赛道的2，剩下八匹马比，如果前一名被淘汰，那就不用比第11次了。

我在这个兄弟的分析后面完善下，应该是10或11次，比如说，第十轮比赛，不要让第四名组的第1名参赛，如果比赛结果是冠军组2.3.4名和第二名组第1名和第三名组第一名中其中三个排前三，那前四名都出来了，不用比第十一轮了。

下面是他前面的分析


虎扑JR1375400214 2019-11-04 14:47 147 亮了 | 灭了 举报 只看此人 引用

专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

引用 @超级lbjLBJ 发表的:
9次
第一组8匹 选出第一
然后第一直接去下一轮和七匹马跑 选最快的
同理 最快的和下面7匹一起跑
877777777
9轮

审错题了 我的锅🐶

引用 @super_wade 发表的:
有死亡之组和水货之组咋办

这个影响不大其实，因为最终只需要找出最快的四匹，每次都是小组前四进的

跑的时候计个时不就行了，8轮。此题终结

引用 @噜噜噜kkk 发表的:
我也是这么想的，跑的慢的不配上跑道

🐎：你行你上啊🐶

引用 @瓜皮君 发表的:
前八在一队你跑完一轮就完犊子了，还那也得这样？跑完第一轮23名都被你淘汰了还需要跑下去？

先看懂别人的回复再反驳

一个回合！
为什么呢？
你就说快不快吧！

引用 @super_wade 发表的:
有死亡之组和水货之组咋办

选前四，死亡之组筛不掉前四，水货之组即使进决赛也排不进前四

引用 @卡安雨 发表的:
这是清华大学2009年自主招生的数学题，当然那个题更复杂一点。这个题目是简化版了，题干没说清楚，应该是不能测速，只能比快慢，怎么比出来最快的4匹马。

这个其实就是在内存限定的情况下进行大量数据排序问题，应该算是外部排序的变种。

先分8组进行8轮排序，每组组内排序已经OK了，然后作为输入，比每组最快的马。这样再需要4次就OK了。

简单想了下，应该还有优化空间，其他jr补充。

引用 @mengtuo7 发表的:
奥运会比法，八八分组，小组前四进下一轮，8+4+2+1共计15回合

那照你这么说的话 88分组 每组取第一名 第9回合就知道谁是最快的前4名了。如果要杠一下的话 第一回合应该是有8组比赛 第二回合就是每组第一跑了 所以2回合就知道前4了。

四次就够了

一个回合，把跑道分成八份，一起跑就完事

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

应该之前是10次，至多11次。9匹马跑的时候，比如留1匹第一名的第四，其他8匹跑，如果第1名的那组第三没进前二，就没有必要第二轮了，反之则11次

一个回合吧，直接一起跑看不出来谁最快吗？

引用 @Mr_Leons 发表的:
那照你这么说的话 88分组 每组取第一名 第9回合就知道谁是最快的前4名了。如果要杠一下的话 第一回合应该是有8组比赛 第二回合就是每组第一跑了 所以2回合就知道前4了。

可是要选的不是前二吗。。。

引用 @夏雨夜雪 发表的:
这个肯定不是最少的

忘记狗头了

引用 @这不是拉风的昵称 发表的:
有个问题，在无法测速的情况下，如何给第二、三、四名组排序呢

组内排序看第一轮，组间排序看第二轮啊

引用 @心远 发表的:
马已经累死了。。。

都得跑拉稀了

引用 @滚去养猪呐 发表的:
如果前八正好就是在同一组呢

那就是冠军组的1234名

引用 @终恋ez 发表的:
充会员一回合就能选出来，不充会员选不出来。

你被录取了

引用 @mengtuo7 发表的:
奥运会比法，八八分组，小组前四进下一轮，8+4+2+1共计15回合

万一有的组最慢的比另一组最快的还要快咋办啊😅

一起跑，找64个人掐表

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

既然是八个赛道，能不能考虑接力🐶

引用 @Mr_Leons 发表的:
那照你这么说的话 88分组 每组取第一名 第9回合就知道谁是最快的前4名了。如果要杠一下的话 第一回合应该是有8组比赛 第二回合就是每组第一跑了 所以2回合就知道前4了。

。。选最快的四匹马啊，八进四是因为筛出去的马一定不是前四，以此类推最终一次比赛留下来的前四名肯定是所有马的前四了。按你说的这样每组留一只万一前八的马分到一组不是出问题了。。

引用 @JimkenCD 发表的:
选前四，死亡之组筛不掉前四，水货之组即使进决赛也排不进前四

对对对，之前没仔细读题

引用 @镰刀死神杜 发表的:
这个影响不大其实，因为最终只需要找出最快的四匹，每次都是小组前四进的

对对对，之前没仔细读题

引用 @用户1105393614 发表的:
这个算法可以优化吧，八个赛道从两头向中间跑，八个赛道可以一次跑16匹马，前八次可以简化成四次。

照你这么说岂不是一回合就够了 跑道均分为八段64匹🐎同时开跑😂

引用 @纯白交响曲 发表的:
万一有的组最慢的比另一组最快的还要快咋办啊😅

忘了加狗头，然后说奥运会比赛，运气很重要

跑四次。假设跑道是直的做够长，大于两倍测速的距离。八条跑道起点马屁股对着放十六匹马，跑四次，得到最快的四匹马。不会有第二次跑的时候马体力的影响

引用 @在水里游泳的恐龙 发表的:
第一次分组跑的，不同组的怎么比较？

还是说详细点会好一点，题目要求决出前四，第一轮分八组，开始的时候我们什么都不知道，但是我们跑完了就能知道每组最快的一个，然后拿这八个去跑出前四，这时候的前四意味着他们会快过后四和后四所在组的2-8名，然后同时我们也知道了这64匹马中谁是最快的了，这里标记一下这四匹马分别是ABCD好了，我们现在要选的234名，那么候选就剩下了A组的234，因为我们不知道这234是不是比B1快，然后B组则是123进入候选，因为我们只需要选四匹，接下来是C组但是C1不可能是第二快因为至少B1要比C1快，所以C组只取12候选，最后还剩D组只用考虑D1了，这样就还剩9个候选，我们要选其中最快的3匹，然后问题的关键在于10次到底够不够，我的理解是不够，因为这里是比较范围从九匹马缩小成八匹马，而只能用第三去排除其对应排名更靠后的马而不能通过第四去确定排名更靠前的马，举例的话就是假定A2是第三快的马的话那么A3和A4一定更慢，但假如A3是第四快的马的话那么A2并不一定快过BCD组的马因为他们都比A1要慢，所以在最后一步9匹马决出前三的比赛中，只要被取除的马对应的前一匹马不是第三，就无法确定被取出的那匹马是否比所在的第三名的马慢，因此存在十次出结果的可能但是十一次一定可以出结果

拿个计时器，八个回合搞定🐶

引用 @单手打爆乔丹 发表的:
信息论吧

正解

@灰灰姑凉

引用 @让你吃含笑半步癫 发表的:
这题，我会，吴军老师讲过，分8组，比8次，在决赛比一次，找到最快的马，然后冠军组里2,3,4与决赛的2,3,4,决赛第二名组里的2，3名，比一次就可以找到跑的最快得第二和第三，找第四再比一次，一共11次

用败者树

选出的不一定是对的，马每一次跑的速度不一样啊，多跑几次估计体能也有影响

引用 @大大霸 发表的:
跑四次。假设跑道是直的做够长，大于两倍测速的距离。八条跑道起点马屁股对着放十六匹马，跑四次，得到最快的四匹马。不会有第二次跑的时候马体力的影响

不对(~_~;)。。。。。

引用 @说气人不你 发表的:
明天报道

那头叫化腾的跑得最快，叫云的最后一名🐶

引用 @有全体信息 发表的:
题干不完整，完整题目应该加多一句，缺少计时器的情况下

还得加一句，每一匹马每次跑的速度一样

二分法不去

12次，把64分成8组，先每组跑一下，记录名次(总共8次)，然后把每组第一名拿出来跑，选出总体第一名，然后再把第一名那组的第二名拿出来跟别组第一名跑，选出总体第二名，以此类推，最后选出总体前四名。
最后需要8+4=12次

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

我觉得跑8次，记时就行了。

引用 @我爱刘懿文 发表的:
15？

冒泡，我一开始也是这么想的

这不就是考察算法问题嘛，冒泡法排序

买个计时器跑八次

引用 @说气人不你 发表的:
明天报道

还是自己亲自骑比较好

引用 @小冰狗 发表的:
那头叫化腾的跑得最快，叫云的最后一名🐶

你也一起来报道

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

你不专业啊 有个兄弟说法很有道理 随机抽一匹马 剩下的63匹马分别和他跑9次 只把这匹马前边的留下来 如果运气好，随机抽中的马是第四或者第五 那么9次就搞定了

10次

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

牛批，感觉没啥问题

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

冠军连续跑那么多次，万一累死了怎么办

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

啊，我只想到15次跑完

经一jr提点 发现可以做到9次筛选出前四
随机抽取一匹马
剩下63只马和它跑9次
只留下这匹马前面的马
如果正好抽中的马是总排名的第四位或者第五位
那么我们就成功的选出了四匹最快的马
问的是最少跑多少次
只要运气好那就跑的少

引用 @说气人不你 发表的:
明天报道

马上报到

引用 @说气人不你 发表的:
明天报道

那是上班，位置收拾好了

引用 @说气人不你 发表的:
明天报道

一个回合，没说跑道多长，把跑道分成8段，看哪4匹马先到达等距离的终点

引用 @说气人不你 发表的:
明天报道

当场录取

引用 @Mr_Leons 发表的:
那照你这么说的话 88分组 每组取第一名 第9回合就知道谁是最快的前4名了。如果要杠一下的话 第一回合应该是有8组比赛 第二回合就是每组第一跑了 所以2回合就知道前4了。

兄弟 你想的太简单了 按照你第一种说法 有可能第二组跑的最快都比第一组跑的最慢的还慢 那你取各组第一还能是前四吗

算法题，最大堆

引用 @可爱可爱超可爱 发表的:
你的马是二维马吗？哪里排的下……

哈哈哈哈老哥你戳中我笑点了 笑死我了

引用 @纯白交响曲 发表的:
万一有的组最慢的比另一组最快的还要快咋办啊😅

杠一下 要的是最快的四匹马 不管小组第八多快，它一定不是最快的四匹之一

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

是的，很清晰。
跑到第10组时也可能提前出结果了，第9组也即冠军组的第四名不跑第10组，如果第9组冠军组的二三名在跑第10组时是一二名，那才需要第11组，否则就提前结束了。

就是考算法的剪枝技巧……

引用 @我要跑路啦 发表的:
算法题，最大堆

不对，想错了

十次，64匹马分成八组 一共八次 将八组的第一拉出来赛一次 第一直接决出 后四位所在的组直接淘汰 最后一次 第一组的234 第二组的123 第三组的12 第四组的1 决出前三就是234名

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

我实在太菜了，第二名组的前三名怎么来的😪

引用 @小冰狗 发表的:
那头叫化腾的跑得最快，叫云的最后一名🐶

不行的话UC录取你

引用 @说气人不你 发表的:
明天报道

不是，跑马没有计时人员吗😊

引用 @北京邮电大学学生处 发表的:
十次，64匹马分成八组 一共八次 将八组的第一拉出来赛一次 第一直接决出 后四位所在的组直接淘汰 最后一次 第一组的234 第二组的123 第三组的12 第四组的1 决出前三就是234名

算了一下，应该得十一次

引用 @虎扑JR1375400214 发表的:
专业点，毕竟不是985一条街，一共跑11回合就OK了。
先随机分8组，取出每组前4。
然后让这8组的冠军跑一轮，留下前4名，这时候冠军已经确定了。剩下的4组舍弃。
然后取出冠军组的2,3、4名，
第二名组的1,2,3名
第三名组的1,2名
第四名组的1名。

这9匹马跑两次，取出前3就OK

8+1+2=11次

你这个是在任何情况下都能找到，但是运气好的话最少10个就找出来了，题目应该是最少几次一定能找出来。

引用 @让你吃含笑半步癫 发表的:
这题，我会，吴军老师讲过，分8组，比8次，在决赛比一次，找到最快的马，然后冠军组里2,3,4与决赛的2,3,4,决赛第二名组里的2，3名，比一次就可以找到跑的最快得第二和第三，找第四再比一次，一共11次

这样是取每一组的第一名吗？如果有一组的前四名是这64屁里最快的，但是你只取了第一名，这样不太对啊。

offer需要小马哥签字吗

引用 @宽粉条 发表的:
一条跑道上八匹马。

我tm乐死了

计时不可以吗

引用 @怒念紧箍咒 发表的:
这个其实就是在内存限定的情况下进行大量数据排序问题，应该算是外部排序的变种。

先分8组进行8轮排序，每组组内排序已经OK了，然后作为输入，比每组最快的马。这样再需要4次就OK了。

简单想了下，应该还有优化空间，其他jr补充。

不对啊兄弟 假设跑的最快的四个全在第一组里 你取每组的第一能取得全部的前四吗