求助一道算法题目

求助一道算法题目

有 n 个任务,序号从 1 到 n,每个任务需要的编辑时间为ti分钟。小明和小白需要在对其中k 个任务中进行编辑。编辑的过程如下: n 个任务按照顺序排列,他们删除 n-k 个任务,不改变剩下的k 个任务的顺序。然后小明选取全部任务的前面一部分任务(可能不选或所有任务),小白选取剩余的。相当于将任务从某个位置分割成两部分,第一部分给小明,第二部分给小白。
之后他们分别对各自的任务进行编辑,编辑需的时间取决于两者中较长的那个。
请帮助小明和小白选择任务和分割片式使编辑尽可能早地完成。

我的第一反应是每次都删最大的,但是我想到一个反例:20 5 19 1 10,k=4,如果删20的话结果为24,但是删19的话结果为20,所以从大往小删是错的
各位大神如果有思路就只说一下思路就好啦,谢谢大家!
全部评论
共有n个数,考虑n+1种分割方法,在每种分割方法内存在左右两个子数组,每次将总和大的那一侧的最大值移除直至剩余共k个数 可以用前缀和数组简化求和工作,但总的时间复杂度是n2,不知道有没有更优的解法
点赞 回复 分享
发布于 2024-10-11 22:49 广东
9.18深信服笔试原题最后一题就是这个,我是直接选出最小的 k 个然后找,但只能过 60%,像你说的这种情况确实过不了:)
点赞 回复 分享
发布于 2024-09-18 21:26 广东
不要从删的角度去考虑,思考删完n-k个任务之后剩下的k个任务是什么,答案一定是排序后最小的k个任务,用反证法可以证明
点赞 回复 分享
发布于 2024-09-13 17:06 广西

相关推荐

07-11 11:10
门头沟学院 Java
请问各位大三兄弟们跟hr说多久实习时间到时候可以提前跑路吗?
程序员小白条:问就是六个月以上,可以一年,实习都这样,你入职后想跑就跑
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-10 12:10
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
醉蟀:你不干有的是人干
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 14:08
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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