gaojx level
获赞
35
粉丝
2
关注
5
看过 TA
2
复旦大学
2022
Java
IP属地:未知
暂未填写个人简介
私信
关注
2021-09-25 18:13
已编辑
复旦大学 Java
只统计代码题,4道题,每题20分 第一题:旅游路线 第二题:立方碑 第三题:水桶效应 第四题:分小组,求最小极值
牛客932775617号:第一题就把图建起来就可以; 第二题用暴力遍历,因为最大也才 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)。
投递美团等公司10个岗位 >
0 点赞 评论 收藏
分享
2021-04-18 17:47
已编辑
复旦大学 Java
在思考的小飞象很深情:测试用例都是对的,提交就是0%,做的我心态炸了,我太难了😂
投递网易互娱等公司10个岗位 >
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了:
牛客网
牛客企业服务