problem

整数が$N = 2k$個与えられるので$k$組作ってそれぞれの組の差の絶対値の総和を最小化せよ。

solution

sortして隣接するのを組にする。$O(N \log N)$。 それでよいのは組$(a, b), (c, d)$を$a \le b, \; c \le d, \; a \le c$として$b \ge c$なら$b - a + d - c \ge c - a + d - b$であることから示せる。

implementation

#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
a.sort()
result = sum([ a[i + 1] - a[i] for i in range(0, n, 2) ])
print(result)