牛客932775617号
2021-09-25 22:26 test C++
关注
第一题就把图建起来就可以；
第二题用暴力遍历，因为最大也才 2^20 所以没问题；
第三题排序之后从最小的补到倒数第二小，然后再把两个倒数第二小补到倒数第三小，直到m == 0，最多O(n)，所以总共 O(n lg n)；
最后一题动态规划，我只做出来O(n^2 m) 不过也够快了。 dp[ i ][ j ] 代表前 i 个人分 j 组的最小极差和，那么要求的就是 dp[ n ][ m ]。然后转移就是 dp[ i ][ j ] = min (dp [ k ][ j - 1] + maxDiff[ k + 1 ][ i ])，k 从 j - 1 到 i - 1，maxDiff [ k + 1 ][ i ] 数组表示从第 k + 1 到 i 这些人的极差，这个二维数组最先算一下需要O(nm) ， 然后把 dp 做出来要 O(n^2 m)。
查看原帖
2 评论
相关推荐
点赞 评论 收藏
分享
我的offer呢😡：这不才9月吗，26到明年毕业前能一直找啊
，能拿下提前批，转正的，offer打牌的都是有两把刷子的，为什么非要跟他们比。如果别人是9本硕+金牌+好几段大厂实习呢？如果别人是双非通天代呢？如果别人是速通哥呢？，做好自己就行了，我们做不到他们一样提前杀死比赛，但晚点到终点也没啥关系吧
点赞 评论 收藏
分享
10-14 15:17
门头沟学院 运营 点赞 评论 收藏
分享
10-17 10:34
上海大学 算法工程师 
双尔：秋招至此我拿到了三个offer，这几天拿到了秋招最快的一个offer。我之前一直陷在纠结里，感觉像站在分岔路口，不知道往哪走才对。
最终在美团饿了么和京东里面选了美团，毕竟是外卖的老大哥，虽然会比较累，但是一切都是值得的，不说了，我的外卖衣服头盔到了
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 发面经攒人品 #
2708150次浏览 36717人参与
# 产品实习，你更倾向大公司or小公司 #
176038次浏览 1998人参与
# 平安产险科技校招 #
1953次浏览 0人参与
# 26届秋招公司红黑榜 #
2776次浏览 8人参与
# 一汽大众工作体验 #
11932次浏览 23人参与
# 最难的技术面是哪家公司？ #
53412次浏览 882人参与
# 未岚大陆求职进展汇总 #
22627次浏览 102人参与
# 机械人的工作环境真的很差吗 #
23899次浏览 117人参与
# 你认为小厂实习有用吗？ #
93096次浏览 604人参与
# 入职第一天，你准备什么时候下班 #
83962次浏览 459人参与
# 参加完秋招的机械人，还参加春招吗？ #
67538次浏览 596人参与
# 经纬恒润求职进展汇总 #
136087次浏览 1060人参与
# 度小满求职进展汇总 #
7643次浏览 40人参与
# 你有哪些缓解焦虑的方法？ #
36475次浏览 831人参与
# 秋招想进国企该如何准备 #
97021次浏览 483人参与
# 来聊聊机械薪资天花板是哪家 #
146237次浏览 804人参与
# 饿了么求职进展汇总 #
76916次浏览 682人参与
# 我对___祛魅了 #
134459次浏览 743人参与
# 职场捅娄子大赛 #
429311次浏览 4161人参与
# 关于提前批我想问 #
242692次浏览 2284人参与
# 机械人的薪资开到多少，才适合去？ #
134923次浏览 489人参与
# 我的求职进度条 #
134206次浏览 1536人参与