Minimum Total Wire Length

ID: 17087

Type: Default

1000ms

256MiB

Maryam is an electrical engineer designing a wiring plan for a communication tower. The tower has connection points at non‐negative integer coordinates along a straight line. Each connection point is colored either red or blue. A wire can connect any two connection points and its length is equal to the absolute difference between their coordinates. The wiring plan must satisfy the following conditions:

Every connection point must have at least one wire connecting it to a connection point of the opposite color.
The total length of all wires used is minimized.

You are to implement the following function:

$$\texttt{long long min\_total\_length(vector\; r,\; vector\; b)} $$

where:

(r) is a sorted (in ascending order) array of size (n) containing the positions of all red connection points.
(b) is a sorted (in ascending order) array of size (m) containing the positions of all blue connection points.

The function should return the minimum total length of wires required to achieve a valid wiring plan. All formulas are given in LaTeX format.

inputFormat

The input consists of two lines:

The first line contains space-separated integers representing the positions of the red connection points (in ascending order).
The second line contains space-separated integers representing the positions of the blue connection points (in ascending order).

outputFormat

Output a single number which is the minimum total length of wires required for the valid wiring plan.

sample

1 3
10

</p>

#P3837. Minimum Total Wire Length

Minimum Total Wire Length