Problem 1356 --算法实现题 3-1 独立任务最优调度问题(习题 3-3)

1356: 算法实现题 3-1 独立任务最优调度问题(习题 3-3)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $6$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
用 2 台处理机 A 和 B 处理 n 个作业。设第 i 个作业交给机器 A 处理时需要时间ai ,若由机器 B 来处理,则需要时间bi 。由于各作业的特点和机器的性能关系,很可能对于某些i,有ai >= bi ,而对于某些 j,j≠i,有 a j < bj 。既不能将一个作业分开由 2 台机器处理,也没有一台机器能同时处理 2 个作业。设计一个动态规划算法,使得这 2 台机器处理完这 n 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例:
(a1,a2,a3,a4,a5,a6)=(2,5,7,10,5,2);(b1,b2,b3,b4,b5,b6)=(3,8,4,11,3,4)。
算法设计:
对于给定的 2 台处理机 A 和 B 处理 n 个作业,找出一个最优调度方案,使 2 台机器处理完这 n 个作业的时间最短。

输入的第 1 行是 1 个正整数 n, 表示要处理 n 个作业。接下来的 2 行中,每行有 n 个正整数,分别表示处理机 A 和 B 处理第 i 个作业需要的处理时间。

将计算出的最短处理时间输出
6
2 5 7 10 5 2
3 8 4 11 3 4
15

推荐代码 查看1356 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$4 $ms] anonyuser 904350 2022-10-17 13:53:46
内存最少[$1240 $KB] anonyuser 904350 2022-10-17 13:53:46
第一AC anonyuser 904350 2022-10-17 13:53:46
第一挑战 张阳@网络工程152 176349 2017-12-14 00:41:18

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛