T2
题目描述
你有 n 颗处理器,每颗处理器都有 4 个核心。现有 n * 4 个待执行任务,
每个核心只能执行一次任务。
给定两个数组:
长度为 n 的处理器数组,里面的元素表示每颗处理器开始工作的时间。
长度为 n * 4 的任务数组,表示执行每个任务需要执行的时间。
每颗处理器的每个核心是同时工作的,及每颗处理器有4个核心可以处理4个任务(可以从所有任务中任意挑选),你需要计算所有处理器执行完所有任务所需的最小时间。
输入格式
第一行包含一个整数 n,表示处理器的数量。
第二行包含 n 个整数 a
i
,表示每颗处理器开始工作的时间。
第三行包含 4∗n 个整数 b
i
,表示每个任务的执行时间。
输出格式
输出一个整数,表示执行完所有任务所需的最小时间。
输入输出样例
说明/提示
案例解释 1
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器(开始工作时间为 8),
将下标为 0, 1, 2, 3 的任务分配给第二颗处理器(开始工作时间为 10)。
第一颗处理器执行完所有任务需要花费的时间:max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16。
第二颗处理器执行完所有任务需要花费的时间:max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13。
因此,所有任务执行完毕的最小时间是 16。
案例解释 2
最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器(开始工作时间为 10),
将下标为 0, 2, 3, 7 的任务分配给第二颗处理器(开始工作时间为 20)。
第一颗处理器执行完所有任务需要花费的时间:max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18。
第二颗处理器执行完所有任务需要花费的时间:max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23。
因此,所有任务执行完毕的最小时间是 23。
数据范围
测试点
n ai bi 1<=n<=25000 0≤ai ≤10 ^9 1≤bi ≤10^9