P1248 Two-Workshop Manufacturing Scheduling

A factory has received orders for $n$ products. Each product must be processed in workshop A first and then in workshop B. At any moment, each workshop can process at most one product. For product $i$, its processing times in workshops A and B are $A_i$ and $B_i$, respectively. Determine an order to process the $n$ products that minimizes the total processing time. The total processing time is defined as the time from starting the first product until all products have finished processing in both workshops A and B.

- The first line contains a single integer $n$, the number of products. - The second line contains $n$ integers, the processing times of the $n$ products in workshop A. - The third line contains $n$ integers, the processing times of the $n$ products in workshop B.

- The first line contains one integer, the minimal total processing time. - The second line contains one processing order that achieves the minimal total processing time. Output the product indices (from $1$ to $n$) separated by spaces.

Constraints: $1 \leq n \leq 1000$, $1 \leq A_i, B_i \leq 1000$. Translated by ChatGPT 5