08-16 17:07 中南大学 算法工程师 发布于江苏
关注
求助一道算法题目
求助一道算法题目
有 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，所以从大往小删是错的
各位大神如果有思路就只说一下思路就好啦，谢谢大家！
全部评论
BangSamHeung
桂林电子科技大学 C++
不要从删的角度去考虑，思考删完n-k个任务之后剩下的k个任务是什么，答案一定是排序后最小的k个任务，用反证法可以证明
在努力的杰克很苦闷
Java
9.18深信服笔试原题最后一题就是这个，我是直接选出最小的 k 个然后找，但只能过 60%，像你说的这种情况确实过不了：）
Azero_
广东工业大学 C++
共有n个数，考虑n+1种分割方法，在每种分割方法内存在左右两个子数组，每次将总和大的那一侧的最大值移除直至剩余共k个数
可以用前缀和数组简化求和工作，但总的时间复杂度是n2，不知道有没有更优的解法
相关推荐
查看33道真题和解析
投递深圳同为数码等公司10个岗位