求助一道算法题目
求助一道算法题目
有 n 个任务,序号从 1 到 n,每个任务需要的编辑时间为ti分钟。小明和小白需要在对其中k 个任务中进行编辑。编辑的过程如下: n 个任务按照顺序排列,他们删除 n-k 个任务,不改变剩下的k 个任务的顺序。然后小明选取全部任务的前面一部分任务(可能不选或所有任务),小白选取剩余的。相当于将任务从某个位置分割成两部分,第一部分给小明,第二部分给小白。
之后他们分别对各自的任务进行编辑,编辑需的时间取决于两者中较长的那个。
请帮助小明和小白选择任务和分割片式使编辑尽可能早地完成。
我的第一反应是每次都删最大的,但是我想到一个反例:20 5 19 1 10,k=4,如果删20的话结果为24,但是删19的话结果为20,所以从大往小删是错的
各位大神如果有思路就只说一下思路就好啦,谢谢大家!
有 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,不知道有没有更优的解法
9.18深信服笔试原题最后一题就是这个,我是直接选出最小的 k 个然后找,但只能过 60%,像你说的这种情况确实过不了:)
不要从删的角度去考虑,思考删完n-k个任务之后剩下的k个任务是什么,答案一定是排序后最小的k个任务,用反证法可以证明
相关推荐
点赞 评论 收藏
分享
02-25 16:29
齐鲁工业大学 golang
找工作勤劳小蜜蜂:自我描述部分太差,完全看不出想从事什么行业什么岗位,也看不出想在哪个地区发展,这样 会让HR很犹豫,从而把你简历否决掉。现在企业都很注重员工稳定性和专注性,特别对于热爱本行业的员工。
你实习的工作又太传统的it开发(老旧),这部分公司已经趋于被淘汰,新兴的互联网服务业,比如物流,电商,新传媒,游戏开发和传统的It开发有天然区别。不是说传统It开发不行,而是就业岗位太少,基本趋于饱和,很多老骨头还能坚持,不需要新血液。
工作区域(比如长三角,珠三角,成渝)等也是HR考虑的因素之一,也是要你有个坚定的决心。否则去几天,人跑了,HR会被用人单位骂死。 点赞 评论 收藏
分享
03-19 01:17
大连东软信息学院 人工智能
在打卡的大老虎很想潜...:你在找实习,没啥实习经历,技术栈放前面,项目多就分两页写,太紧凑了,项目你最多写两个,讲清楚就行,项目背景。用到的技术栈、亮点、难点如何解决,人工智能进面太难了,需求少。你可以加最新大模型的东西 点赞 评论 收藏
分享
查看11道真题和解析