求助一道算法题目
求助一道算法题目
有 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-k个任务之后剩下的k个任务是什么,答案一定是排序后最小的k个任务,用反证法可以证明
9.18深信服笔试原题最后一题就是这个,我是直接选出最小的 k 个然后找,但只能过 60%,像你说的这种情况确实过不了:)
共有n个数,考虑n+1种分割方法,在每种分割方法内存在左右两个子数组,每次将总和大的那一侧的最大值移除直至剩余共k个数
可以用前缀和数组简化求和工作,但总的时间复杂度是n2,不知道有没有更优的解法
相关推荐