#P1664. 2024.1.30-亚马逊-后端开发机试-第一题

2024.1.30-亚马逊-后端开发机试-第一题

An AWS client has brought servers and databases from data centers in different parts ofthe world for their application. For simplicity, let's assume all the servers and data centersare located on a 1-dimensional line.

You have been given the task of optimizing the network connection. Each data centermust be connected to a server. The positions of n data centers and n servers are given inthe form of arrays. Any particular data center, center[i], can deliver to any particularserver destination, destination/j, The lag is defined distance between a data center atlocation xand a server destination at location y is |x-y|, i.e., the absolute differencebetween xand y. Determine the minimum lag to establish the entire network.

Example

There are n = 3 connections, the positions of data centers, center = [1, 2, 2], and thepositions of the server destinations, destination = [5, 2, 4].

The most efficient deliveries are: The center at location 1 makes the first connection to the server at location 2.

The center at location 2 makes the second connection to the server at location 4.

The center at location 2 makes the third connection to the server at location 5

The minimum total lagis=abs(1-2)+ abs(2 -4)+ abs(2 - 5)=1 + 2 + 3 = 6

Constraints

1n1e51 \leq n \leq 1e5

1center[i],destination[i]1e91 \leq center[i] , destination[i] \leq 1e9

输入描述补充

第一行一个整数n

接下来两行,一行为center,一行为destination

Sample Case 0

Sample Input

5
3 1 6 8 9
2 3 1 7 9

Sample Output

5

ExplanationYou may create the connections as center = [1, 3, 6, 8, 9] destination =[1, 2, 3, 7, 9] Minimum total distance =abs(1 -1)+ abs(2 -3)+ abs(3 - 6)+ abs(7 -8) + abs(9 - 9)= 0 +1+3+1+0=5