7375: 独立任务最优调度问题
[Creator : ]
Description
用 2 台处理机 A 和 B 处理 n 个作业。
设第 i 个作业交给机器 A 处理时需要时间 $a_i$,若由机器 B 来处理,则需要时间 $b_i$。
既不能将一个作业分开由 2 台机器处理,也没有一台机器能同时处理 2 个作业。
设计一个算法,使得这 2 台机器处理完这 n 个作业的时间最短,从任何一台机器开工到最后一台机器停工的总时间。
设第 i 个作业交给机器 A 处理时需要时间 $a_i$,若由机器 B 来处理,则需要时间 $b_i$。
既不能将一个作业分开由 2 台机器处理,也没有一台机器能同时处理 2 个作业。
设计一个算法,使得这 2 台机器处理完这 n 个作业的时间最短,从任何一台机器开工到最后一台机器停工的总时间。
Input
输入的第一行是一个正整数 $n$,表示要处理 $n$ 个作业。
接下来的 2 行中,每行有 $n$ 个正整数,分别表示处理机 A 和 B 处理第 i 个作业需要的处理时间。
接下来的 2 行中,每行有 $n$ 个正整数,分别表示处理机 A 和 B 处理第 i 个作业需要的处理时间。
Output
输出最短处理时间。
Sample 1 Input
6
2 5 7 10 5 2
3 8 4 11 3 4
Sample 1 Output
15