中位数

如果想要使各个点与中心点差值的绝对值之和最小化, 那么这个中心点应该选择这些点的中位值.
这个结论在初中的时候就学过.

多说一句: 如果想要使各个点与中心点差值的平方和最小化, 那么这个中心点应该选择这些点的算术平均值.

时间复杂度

使用了排序, 因此时间复杂度为O(nlogn)
如果使用快速选择算法求中位数, 时间复杂度可以降低到O(n)

Python 代码

N = int(input())
A = sorted(map(int, input().split()))
m = A[N // 2]
print(sum(abs(e - m) for e in A))