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

8个回合啊，咋想的，每匹马计时就好了呀。搞七搞八。🐶

引用 @LightingB 发表的:
杠一下 要的是最快的四匹马 不管小组第八多快，它一定不是最快的四匹之一

哈哈我知道 我是用这个例子来杠一下每个组取最快再比的这种说法的

一快跑，掐表啊，又没说不让掐表

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

第一回合8次，记录下名次，第二回合的从8组第一的拉出来比，第二次比赛后面4名的组全组淘汰，第4名的除第一次第一外组全组淘汰，第3名的组第一回合前二进组，3.4淘汰，第2名的组第一回合前3晋级，第4淘汰，第一名的组，全组晋级，并且2次第一保送，剩下9匹马选前3，可能需要2次，所以总共应该是8+1+2，11次选出前4的马，不知道对不对。

15？

8次啊 买个秒表记个时间就完事了啊

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

可能存在有的小组第四都比其它组第一快，所以第一轮需要取前四

引用 @泉州古大乐 发表的:
第一回合8次，记录下名次，第二回合的从8组第一的拉出来比，第二次比赛后面4名的组全组淘汰，第4名的除第一次第一外组全组淘汰，第3名的组第一回合前二进组，3.4淘汰，第2名的组第一回合前3晋级，第4淘汰，第一名的组，全组晋级，并且2次第一保送，剩下9匹马选前3，可能需要2次，所以总共应该是8+1+2，11次选出前4的马，不知道对不对。

古天乐牛皮，我吴彦祖服了

这跟leetcode上滑动窗口找中位数差不多，先八次把每个组中间值和第一名逼出来，然后只比各组中间值找出最厉害的四组，然后这四组第一和第四正好凑八个比

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

笑死。。

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

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

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

第一次8个比赛 选出最快的4个 参加下一轮 15次比出来 这是我能想到最少的了

最少的9次就可以了，八场小组赛取一组的第四，和其他组的第一比，然后赢了另外7组的头名，结果就出来了。（这是理论上讲最少的回合数）

引用 @虎扑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次

第二名组的1,2,3名，第三名组队1,2和第四名的1，你怎么判断？在不测速的前提，第二名之间没有比较，应该视为一样快，第二名组跑一次才能决出1,2,3，同理第三名组，第四名组也应该跑一次啊？？
真心求解

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

叠罗汉？？

最少是10次，随机分8组跑8次，然后选出8个组的冠军跑1次，最后冠军组第5名和冠军组前4名所在的随机组的第2名跑1次，要是冠军组第5名跑第一，那前4就选出来了。

引用 @遥隔_云端 发表的:
算法题啊。。

9次冒泡排序，取最后四个，不就可以出来了吗。我才大一为什么我觉得挺简单

直接消灭其中60只，剩下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轮结束了，专业点老哥

引用 @hi我等你很久了 发表的:
第二名组的1,2,3名，第三名组队1,2和第四名的1，你怎么判断？在不测速的前提，第二名之间没有比较，应该视为一样快，第二名组跑一次才能决出1,2,3，同理第三名组，第四名组也应该跑一次啊？？
真心求解

就是加上你说的6匹加上冠军组的234 一共九匹，跑两轮 决出前三

引用 @蹿腾吧 发表的:
叠罗汉？？

马体蜈蚣……

引用 @还要更机智的帆帆 发表的:
不用取第四名组的第一名，10轮结束了，专业点老哥

需要第四组的第一名。老哥。专业点

引用 @你好心晴 发表的:
就是加上你说的6匹加上冠军组的234 一共九匹，跑两轮 决出前三

我已经知道了，谢谢老哥

引用 @你好心晴 发表的:
需要第四组的第一名。老哥。专业点

那是在第10轮没结束的时候再取它，10轮结束就不用取了

引用 @遥隔_云端 发表的:
算法题啊。。

本人不是码农。感觉这种程序算法题都是在考数学啊，是不是数学好搞算法优势大。

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

我觉得这兄弟说的没问题啊，回复的是不是没理解。为了避免最快的在同一组，必须每组的前四名都参加下一轮，以此类推一共15轮

是不是12次

1次

哪里有答案，每匹马每次都能达到一样的速度跑吗？那不是马那是得有定速的汽车

11轮

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

想错了。楼下正解

引用 @还要更机智的帆帆 发表的:
那是在第10轮没结束的时候再取它，10轮结束就不用取了

只要不是 第二轮的23 前二，就不用取了。如果是他俩前二，就要把他拿上啦再跑一次

引用 @modafinil 发表的:
最少是10次，随机分8组跑8次，然后选出8个组的冠军跑1次，最后冠军组第5名和冠军组前4名所在的随机组的第2名跑1次，要是冠军组第5名跑第一，那前4就选出来了。

错了是9次，随机分8组跑完，要是其中有一组的都非常快，取这组的第4和其他组的第1再跑一次，要是这组的第4能跑第1，那前4名就选出来了。

引用 @稀饭范贩 发表的:
本人不是码农。感觉这种程序算法题都是在考数学啊，是不是数学好搞算法优势大。

对 算法对数学要求大 所以很多转算法的硕士 什么专业的都有

这个题目没说不能计时吧，8条道轮流出发分别计时不就可以了吗，一次过

引用 @我比丹尼格林三分准 发表的:
1234组的第一已经确定比他们快了

是的😂我搞错了

1个回合。 全部放上去一起跑。前四名最快。

引用 @modafinil 发表的:
错了是9次，随机分8组跑完，要是其中有一组的都非常快，取这组的第4和其他组的第1再跑一次，要是这组的第4能跑第1，那前4名就选出来了。

这么说的话，取这组的45678 跟其他组的第一 跑一遍，赢了就能直接决出来了

引用 @遥隔_云端 发表的:
算法题啊。。

。。。。我果然不适合干程序员

引用 @虎扑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轮就够了呀。每轮跑8只，8轮跑完，按照计时结果选最快的4只啊。

这种题，第一反应就是快排

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

充值会员，随机选取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次

需要隔天比赛, 有些马连续跑, 会饿的没劲!

引用 @虎扑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次

有的马开始即巅峰呢？ 有的马需要慢慢进入状态呢 ？对于马不公平🐶

引用 @我的偶像183 发表的:
那就冒泡排序试试？

等你冒完泡，马嘴巴里都冒泡了

引用 @泉州古大乐 发表的:
第一回合8次，记录下名次，第二回合的从8组第一的拉出来比，第二次比赛后面4名的组全组淘汰，第4名的除第一次第一外组全组淘汰，第3名的组第一回合前二进组，3.4淘汰，第2名的组第一回合前3晋级，第4淘汰，第一名的组，全组晋级，并且2次第一保送，剩下9匹马选前3，可能需要2次，所以总共应该是8+1+2，11次选出前4的马，不知道对不对。

这个靠谱，方向应该是对的，第九次比赛一下淘汰掉一多半马。

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

而且，题目应该是： 至少比多少场， 能够确保可以测出最快的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次

6个回合够了，每匹马亮个相，然后观众短信投票，票最多的前四就是了

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

万一最快的四匹第一轮同在一组怎么破

15

拿个秒表掐着，八个回个全部跑完取前四不就能分出来了吗？算什么算？

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

你这是产品岗的答案。。。

12吧，64匹分8波找出8个第一，然后8个第一比出一个最快。最快这组的第二和剩下的七个第一再跑一局第一的就是64匹中的第二快，以此类推补位。找出前四名需要8+1+1+1+1

引用 @宽粉条 发表的:
一个回合，一起跑，前四就完事。

题都没有读懂就别来秀了吧

概率论

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次

已删除............. [ 此帖被werrwerr在2019-11-04 17:51修改 ]

引用 @Juejima 发表的:
万一最快的四匹第一轮同在一组怎么破

没看到每次进4个么

先跑8次获得每组的名次1-8名，头名跑一次（第9次），确定名次1-8名，第一名铁定是冠军了，然后前四名只会出现冠军组234和亚军组的123，季军组的12，第四名的1，也就是剩下9匹马得到前三就可以了。9匹马两次比赛搞定，所以总共8+1+2=11

跑道均分八段，一起跑

引用 @性感湖人在线撩妹 发表的:
他要最快的4匹马 你都说计时器了 我是不是可以说 每组的第一名看到后面的跑不过它没用全力呢

那是不是还可以说今天这匹马的腿被蚊子咬了，影响发挥

引用 @虎扑JR1892095035 发表的:
9次冒泡排序，取最后四个，不就可以出来了吗。我才大一为什么我觉得挺简单

因为你大一的老师没教你好好读题

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

照你这么"优化"，就没有答案了。

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

题干肯定是至少几次可以肯定测出来， 所以答案是11

n>log(C(64,8))/log8

不会做，会抄

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

别明天了，现在就来

八个回合。用个计时器就可以了🐶

需不需要考虑马匹疲劳对速度的影响？如果不考虑还能想想

引用 @Kevindavid 发表的:
所以咱们用堆排序？

堆排序好像更慢

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

借楼，分三轮进行
第一轮分八组，每组八匹，记下每组前四;
第二轮，第一轮的每组第一组成第九组跑一轮，记下前四;
第三轮 第九组的1名和2名所在原小组的234名共6匹加上第九组的三四名组成第十组跑一轮，记下前二
第九组的前二加上第十组的前二就是最快的四匹🐎了，一共用了8+1+1=10个回合。

引用 @泉州古大乐 发表的:
第一回合8次，记录下名次，第二回合的从8组第一的拉出来比，第二次比赛后面4名的组全组淘汰，第4名的除第一次第一外组全组淘汰，第3名的组第一回合前二进组，3.4淘汰，第2名的组第一回合前3晋级，第4淘汰，第一名的组，全组晋级，并且2次第一保送，剩下9匹马选前3，可能需要2次，所以总共应该是8+1+2，11次选出前4的马，不知道对不对。

第二回合因为第一组第一名已经保送，只需要拉第一组234名和第二组123名和第三组的12名比赛选前三即可，一共只需要九次，不知道对不对

引用 @欢乐小松 发表的:
第二回合因为第一组第一名已经保送，只需要拉第一组234名和第二组123名和第三组的12名比赛选前三即可，一共只需要九次，不知道对不对

一共十次，说错了

引用 @梁棋政 发表的:
没看到每次进4个么

我瞎了

引用 @谨言慎行p 发表的:
不对啊兄弟 假设跑的最快的四个全在第一组里 你取每组的第一能取得全部的前四吗

每组第一的一起跑，跑完选出最快的，假设是a组，此时把a组第二拉出来，和原来七个跑，再把最快的拉出来，以此类推，前一个最快的选出来，该组下一名顶上，选出四个最快的，这种方法就是跑12次，不知道还有没有更快的，坐等

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

你这个要量距离吧。和计时也差不多了。

既然问最少，当然是九个回合了

64分八组，最优状况就是8个每组第一正好是前八名

最后前8再来一组分出前四。。

完美。。。

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

收拾收拾跟我去你座位吧

引用 @欢乐小松 发表的:
第二回合因为第一组第一名已经保送，只需要拉第一组234名和第二组123名和第三组的12名比赛选前三即可，一共只需要九次，不知道对不对

我第四组第一名没有排面的吗🐶

引用 @就是叉哥 发表的:
我第四组第一名没有排面的吗🐶

好吧，没注意，哈哈，还是11次

8号打假赛的提前倒下

最少13个回合可以选出最快的4匹马，8+3+1+1

两个回合吧……对不对

引用 @极夜之辰 发表的:
借楼，分三轮进行
第一轮分八组，每组八匹，记下每组前四;
第二轮，第一轮的每组第一组成第九组跑一轮，记下前四;
第三轮 第九组的1名和2名所在原小组的234名共6匹加上第九组的三四名组成第十组跑一轮，记下前二
第九组的前二加上第十组的前二就是最快的四匹🐎了，一共用了8+1+1=10个回合。

看了jr们的答案我果然还是不够严谨

8+4+2+1，15次，分组，每次跑满8个跑道，淘汰后四名，每轮淘汰一半，完事

我知道有一匹，它叫马化腾😏😂

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

啥云？腾讯云吗

引用 @纯白交响曲 发表的:
哈哈我知道 我是用这个例子来杠一下每个组取最快再比的这种说法的

你不是杠一下，你是没理解。

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

1. 题目没说不能测速
2. 干跑误差太大，应该至少跑个几次统计成绩吧

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

我最少要13次，看了你的，牛逼，你的可能才是最少的

不是8次？分8组跑 掐秒取最快的四个啊

引用 @一块奶油小饼干 发表的:
每组第一的一起跑，跑完选出最快的，假设是a组，此时把a组第二拉出来，和原来七个跑，再把最快的拉出来，以此类推，前一个最快的选出来，该组下一名顶上，选出四个最快的，这种方法就是跑12次，不知道还有没有更快的，坐等

你这个办法可不止12次。

引用 @60E守卫者 发表的:
最少13个回合可以选出最快的4匹马，8+3+1+1

3哪里来的？

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

是的，所以这种题目通常第一步是补充完整题干，比如没有计时器，马每次都同时起跑，每次都跑得一样快，不存在几匹马并列冲线。。。
最后一般问的是，至少要多少轮才能确保测出最快的马。

引用 @梁棋政 发表的:
没看到每次进4个么

请问第二轮，最快的三个在一组怎么破

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

还得充年费会员

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

我觉得是最多9次。前八次一样，找本组最快的四匹马。第九次：每组前四按照快慢列竖队，小组成绩快的排在该道的前面，慢的在该道后面，等于是32匹马一起跑。然后最快的四匹就一目了然了，因为小组慢的马是不会超过前面小组快的马。（用这个方法找最快的前八也是9次）