线性代数 + 中位值

直接用了”七夕祭”题目的算法:
https://www.acwing.com/problem/content/description/107/

时间复杂度

利用sort求中位数, 因此, 时间复杂度是O(n*log(n))
如果通过快速选择来求中位数, 时间复杂度为O(n)

Python 代码

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
avg = sum(a) // n
for i in range(n):
    a[i] -= avg
for i in range(1, n):
    a[i] += a[i - 1]
a.sort()
median = a[n // 2]
print(sum(abs(e - median) for e in a))