Attack on Daleks

0

0 votes
Easy
Problem

The Doctor is approaching a Dalek spaceship. Daleks needs to position themselves such that they can maximise the strength of their force field in order to defend themselves. There are N Daleks on the ship and each one is having some initial distinct position and there are N distinct final positions which needs to be covered by one and only one Dalek. All initial and final positions are such that they lie on a straight line. We assume the line to be x-axis. You are given initial positions of all the N Daleks and N final positions that needs to be covered. You need to calculate the minimum sum of distances covered by each Dalek.

Input Format:

First line consists of the number of Daleks, ie, N.

Second line consists of the initial distinct positions(x co-ordinate) of all N Daleks.

Third line consists of N distinct final positions(x co-ordinate).

Output Format:

Output the minimum possible sum of distances for each of the Daleks to occupy a final position.

Constraints:

1N106

109 X co-ordinates 109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Minimum sum of distances can be achieved when Dalek with x co-ordinate -2 occupies x xo-ordinate 1, one with x co-ordinate 4 occupies 2 and the one with x co-ordinate 5 occupies 3.

Total distance will be |1 - (-2)|+|2 - 4|+|3 - 5| = 7.

Editor Image

?