帆软笔试第2道编程题怎么做

N比赛轮数,K阈值,R评分数组
2^N场比赛 根据评分  评分高的人必胜
要求:评分前两名 决赛对决
评分前四名  半决赛
评分前八名  1/4决赛
。。。
如果对决的差值大于阈值K,则称该场次为势均力敌的比赛
问最多能有多少场势均力敌的比赛?
好难啊🤯 #笔试#
全部评论
刚做完,居然AK了,题目条件是尽量公平,也就是前两名一定进决赛,前四名一定进四强,以此类推。所以可以先排序,降序,每打一轮数组就减少后面一半的人(当然这里数组没有必要真的删掉后一半,遍历的时候每次缩小一半即可),遍历所有轮数(log2N),每一轮枚举前一半和后一半的比赛情况(前一半 * 后一半 O(n2)),看是否小于等于阈值K,这里的枚举可以用到大量的剪枝,因为已经排好序了,第一个剪枝,如果一旦前一半某个数和后一半某个数差值小于K,说明已经匹配好了,ans++,直接退出,枚举前一半下一个元素,第二个剪枝,如果前一半某个数和后一半某个数差值已经大于K了,也直接退出,因为是降序,后一半某个数后面的数只会更小,再和前面的比较更会大于K了,直接退出,我是两个剪枝后就AK了
2 回复 分享
发布于 09-04 21:21 吉林
请问帆软笔试是链接失效前随便找个时间做都行吗?刚收到邮件
点赞 回复 分享
发布于 09-05 17:16 上海
排序后直接贪心就100%,复杂度应该是O(nlogn) + O(n) ps:O(nlogn) + O(n) + O(n/2) + O(n/4) + ....
点赞 回复 分享
发布于 09-24 15:36 四川

相关推荐

10-23 10:31
门头沟学院 Java
—大红 字节:流程迅速,是挂是过都很快,就是手撕存在斩杀机制压力大。携程(线下):线下流程井井有条,还有叫号面试系统,还包午饭,有小零食,面试难度也很友好。美团:流程推进也很快,同时面试官介绍业务很耐心,非常赞,大家都夸团子不是没道理的!—小红pdd(线下):流程很快,面试过程也很不错,面试官也耐心介绍pdd的工作,就是线下有流程一点点混乱,然后面试强度的不低。京东:流程也比较快,面试难度友好,就是线下hr面比较难顶,当日通勤来回4+小时,横穿上海。滴滴:一天三面,面试难度友好(可能是kpi面),因为约面晚,我个人也觉得是备胎。xhs:今年薪资开得特别高,缺点就是池子太大,一旦泡出来就被大包砸晕,比较遗憾,我说不想做tob业务,直接被挂了,后悔了,这么大包,我扫厕所也行的。—小黑慢脚:大家诟病的泡池子机制,而且在一面结束后,二面约在了2周后,很明显的扩大池子的嫌疑。hr面后泡池子中,已经泡了一个月,泡成巨人观了。🐜:业务面hr面流程超级快,hr面后泡了一个半月池子了,还没有消息。—大黑同花顺:一面说需要提前实习,二面说必须得实习转正,婉拒了,过了两月问“给正式offer什么时候来实习”,我说有毕业论文,暂时去不了,然后又没了。xp汽车:拼手速抢面试时间,手慢无,睡觉错过了,最近开薪资了,好像也不怎么给力。
Twilight_m...:字节拿人简历刷kpi面不匹配岗位,还有部门锁简历,这还能给大红
26届秋招公司红黑榜
点赞 评论 收藏
分享
评论
1
7
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务