两道工序排单

普及-⏱ 1000ms💾 256MB#P3227🏷️ 排序贪心

题目描述

食堂接到 $n$ 份菜品订单,每份菜必须先经过灶台 A 再经过灶台 B 两道工序。 第 $i$ 份菜在 A、B 两道工序各需 $A_i, B_i$ 分钟,工序一旦开始便不可中断, 同一灶台同一时刻只能处理一份菜。合理安排加工顺序,使从开始处理第一份菜 到所有菜完成两道工序的总时间最短。输出最短总时间和一种最优加工顺序。

输入格式

第一行一个整数 $n$; 第二行 $n$ 个整数 $A_1 \ldots A_n$; 第三行 $n$ 个整数 $B_1 \ldots B_n$。

输出格式

第一行一个整数:最短总时间; 第二行 $n$ 个整数:一种最优加工顺序(菜品编号)。

数据范围

$$1 \le n \le 2000$$
,$1 \le A_i, B_i \le 1000$。

样例输入 #1
4
2 4 3 6
5 1 3 2
样例输出 #1
16
1 3 4 2
样例输入 #2
1
7
3
样例输出 #2
10
1