锁定老帖子 主题:讨论一个算法,GOOGLE的一个面试题
精华帖 (8) :: 良好帖 (2) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2008-10-29
yuyoo4j 写道 是7场;
前面5场,让所有的马跑一次; 标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队 标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队 第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5; 第7场, 让 第6场中跑第1,3,5名的马对应在 first梯队 和 第2,4名在second梯队跑一次 就可以最终确定 前5名马了. 貌似你是把前五名限制在了每场的第一二名里共10匹马中间 如果第一场比赛的五匹马碰巧就是最快的五匹马呢? |
|
返回顶楼 | |
发表时间:2008-10-29
yuyoo4j 写道 是7场;
前面5场,让所有的马跑一次; 标记每场的第一名为: A,B,C,D,E; 标记此5匹马为 first梯队 标记每场的第二名为: a,b,c,d,e; 标记此5匹马为 second梯队 第6场, 让 second梯队 跑一次; 标记 顺序为 1,2,3,4,5; 第7场, 让 第6场中跑第1,3,5名的马对应在 first梯队 和 第2,4名在second梯队跑一次 就可以最终确定 前5名马了. 这样好像也不能确定哦。假如有一种情况就是在分组的时候正好把前五名分到一个队里,其实这种情况就好比说,几个班的人比赛,每个班谁最利害是知道了,但是有可能其中一个班的人比其他班里的第一名都要厉害(比如那些特尖班奥赛班之类的,呵呵)!不妨说这队为甲队吧,其他依次为乙丙丁戊。按你这种思路,第六场跑第一的是甲队的第二(实则也是整体第二),而其实真正的第三第四名第五都还在甲队呢,能确定在第七场的时候把前五都选出来么? |
|
返回顶楼 | |
发表时间:2008-10-29
1,先赛五场
2,第六场,每场的第一名赛一次,此次的第一名拿出去 3,第七场,第六场第一名在(1)里队伍的第二名顶上来再加上第六场的剩下四名比赛,此次的第一名再拿出去。 4,第七场的第一名在(1)里的下一个名次的马继续顶上来,和剩下的四匹马比赛 这样算下来得赛10场,不知道对不对 我表述的太烂了。。。sigh,自己寒一个 |
|
返回顶楼 | |
发表时间:2008-10-29
第六场: 甲1 乙1 丙1 丁1 戊1 每队队员分别称为甲1,甲2,。。。乙1,乙2.。。。丙1,丙2。。。。。 甲1为No1选出
甲2-甲5 4名队员:可能争夺的名次:2 3,4,5, 乙2-乙4 3名队员:可能争夺的名次: 3,4,5, 丙2-丙3 2名队员:可能争夺的名次: 4,5, 丁2: 1名队员:可能争夺的名次: 5, 戊: 其他四名被淘汰; 除甲1(已选出),加上乙1,丙1,丁1,戊1,共剩下14匹马仍需比赛 第七场: 乙1 甲2(争第二名,因为只有甲2有实力和乙1抗衡) 丙1 甲3 乙2(争第三名) 若比赛结果为: 甲2 第二,甲3第三(也就是第七场比赛的第一第二名,是整体第二第三名) 那么乙3,乙4,丁1,丁2,戊1被淘汰(被甲2,甲3挤掉) 甲队仍需比赛队员::甲4,甲5, 乙队仍需比赛队员: 乙1,乙2, 丙队人需比赛队员: 丙1 共5名队员仍需参加比赛 因为只剩下5名需要再参加比赛的马了,所以最多只要再赛第八场就可出结果了。取第八场的前两名,再加上前面已赛出来的甲1,甲2,甲3,便可选出整体的前五名。 还有其他情况,不过场次应该都要更多或相等的吧。 |
|
返回顶楼 | |
发表时间:2008-10-29
感觉最少需要6+1+4场比赛,前5场找出每组中的最快的,第六场找出选拔出来的最慢的,剩下的四场和余下的四对比证明自己最快
|
|
返回顶楼 | |
发表时间:2008-10-29
superloafer 写道 M6正好跑了第一名,第七场就能出结果了,前五名就是在第六场比赛的五匹马; 我觉得这样不对~。 如果是以下情况怎么办?(数字代表马的速度) 第一场:25 9 8 6 5 第二场:17 12 13 7 4 第三场:24 14 15 16 22 第四场:23 18 19 20 21 第五场:11 10 3 2 1 这样最快的是 21 22 23 24 25 可是按LZ所说的 那就是 23 24 25 11 17 |
|
返回顶楼 | |
发表时间:2008-10-29
这个答案我早已经承认错误了啊,呵呵!看来目前离google的距离还挺远,平时要多看看这类题目,多多锻炼算法和思维。
|
|
返回顶楼 | |
发表时间:2008-10-29
思考了一下这个问题,发现一个规律就是:从第六场决出每队最快的马之后的每一场比赛中,跑得越前的马都给它原来所在队的队员留下了更广阔的空间,而同时也让其他的某些队员无缘下一轮比赛。比如说第六场,甲1跑了第一,那么给甲2,甲3,甲4,甲5留下了广阔的发展空间,它们都有可能有能力得的2,3,4,5名,他们四个当中至少要有一个上过场,否则就算接下来比了N场,他们没上场都不能定音。所以最快决出前五名的马的规则就是要让每场跑第一名的马所属的那队其他马先上。它在比赛中所获的名次,决定其后面兄弟的命运。比如甲2,甲3在第七场分别跑了第四第五,甲队是不用再比赛了,甲2,甲3跑的成绩好一点,那么给甲4,甲5留下了余地,也淘汰了一些其他队的一些队员。
|
|
返回顶楼 | |
发表时间:2008-10-30
既然都很稳定,拿个秒表计算,看时间,只要比五场就知道结果了!!
哈哈。。。大家不要扔砖头。。。 |
|
返回顶楼 | |
发表时间:2008-10-30
没什么说的了,就是10场了,上面已经有人说过了,是正确的了!
|
|
返回顶楼 | |