求助一道算法题目

求助一道算法题目

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

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

相关推荐

佛系的本杰明反对画饼:个人看法,实习经历那段是败笔,可以删掉,它和你目标岗位没什么关系,没有用到什么专业技能,甚至会降低你项目经历内容的可信度。个人技能那里可以再多写一点,去boss直聘上看别人写的岗位要求,可以把你会的整合一下,比如熟悉常规的开关电源拓扑结构(BUCK、正激、反激、LLC等),熟悉常用的通信总线协议和通信接口,如UART,IIC,SPI等。简历首先是HR看的,HR大多不懂技术,会从简历里去找关键字,你没有那些关键字他可能就把你筛掉了,所以个人技能尽量针对着岗位描述写一下。还有电赛获佳绩,获奖了就写什么奖,没获奖就把获佳绩删了吧,要不会让人感觉夸大。
点赞 评论 收藏
分享
昨天 17:35
门头沟学院 C++
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务