Given two arrays of N integers, pair every value in the first array with one value in the second so that the sum of absolute differences is minimized.
Sort both arrays in nondecreasing order and pair elements at the same indices. To see why this is optimal, consider two first-array values x <= y and two second-array values u <= v. Pairing them in the same order costs |x - u| + |y - v|; crossing them costs |x - v| + |y - u|. The same-order cost is never greater: on the number line, matching ordered endpoints avoids the extra distance introduced by crossing. Therefore any crossed pair can be uncrossed without increasing the total, and repeatedly uncrossing yields the sorted, rank-by-rank pairing.
The arrays are sorted in O(N log N) time, followed by one linear pass. The total running time is O(N log N) and the arrays use O(N) space. Cast to long before subtracting: two valid int values can have a difference larger than Integer.MAX_VALUE, and the total may also exceed the int range.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return sign * value;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for (int i = 0; i < n; i++) a[i] = input.nextInt();
for (int i = 0; i < n; i++) b[i] = input.nextInt();
Arrays.sort(a);
Arrays.sort(b);
long total = 0;
for (int i = 0; i < n; i++) {
total += Math.abs((long) a[i] - b[i]);
}
System.out.println(total);
}
}