Description

Maryam is an electrical engineer. She is designing a wiring plan for a communication tower. There are connectors placed at various heights on this tower. A wire can be used to connect any two connectors. Each connector may be connected to any number of wires. There are two types of connectors: red connectors and blue connectors.

For convenience, the tower is regarded as a straight line, and the red and blue connectors are located at some non-negative integer coordinates on this line. The length of a wire is the distance between the two connectors it connects.

Your task is to help Maryam find a wiring plan that satisfies the following:

1. Each connector has at least one wire connected to a connector of the opposite color.
2. The total length of the wires is minimized.

Implementation details:

You need to implement the following subroutine:

long long min_total_length(std::vector<int> r, std::vector<int> b)

• $r$: an array of length $n$, containing the positions of all red connectors in ascending order.
• $b$: an array of length $m$, containing the positions of all blue connectors in ascending order.
• This subroutine should return the minimal total length of wires among all valid wirings.
• Note that the return type of this subroutine is long long.

Constraints:

• $1 \leqslant n,m \leqslant 100000$.
• $0 \leqslant r[i] \leqslant 10^9$ (for all $0 \leqslant i \leqslant n-1$).
• $0 \leqslant b[i] \leqslant 10^9$ (for all $0 \leqslant i \leqslant m-1$).
• The arrays $r$ and $b$ are already sorted in ascending order.
• All $n+m$ values in $r$ and $b$ are distinct.

Subtasks:

1. ($7$ points) $n,m\leqslant 200$.
2. ($13$ points) All red connector positions are smaller than any blue connector position.
3. ($10$ points) In every $7$ consecutive connectors, there is at least one red connector and one blue connector.
4. ($25$ points) All connectors have distinct positions in the range $[1,n+m]$.
5. ($45$ points) No additional constraints.

Input Format

You need to implement the subroutine described above.

Output Format

Return a long long value.

r = [1, 2, 3, 7]
b = [0, 4, 5, 9, 10]

10

Hint

Sample function call:

min_total_length([1, 2, 3, 7], [0, 4, 5, 9, 10])

The following figure illustrates the sample data.

• The tower is drawn horizontally.
• Because the statement is printed in black and white, red connectors are drawn darker, and blue connectors lighter.
• There are $4$ red connectors at positions $1, 2, 3$, and $7$.
• There are $5$ blue connectors at positions $0, 4, 5, 9$, and $10$.
• The optimal total wire length is $1+2+2+2+3=10$, so the subroutine should return $10$.
• Note that there are two wires incident to the connector at position $7$.

Translated by ChatGPT 5