排序 + 中位数

根据距离公式, 容易发现水平距离之和和垂直距离之和可以独立计算.
分别让水平距离之和最小化, 垂直距离之和最小化, 就可以得到距离之和最小化.
垂直距离之和非常容易, 排队后的y坐标应该为所有点的y坐标中位数.

水平距离之和有一点点复杂:
第一: 容易发现排队前后的x坐标的排名应该是不变的.
通过反证法容易证明这一点.
如果两个元素在排队后, 排名发生了变化, 对这两个元素的位置进行交换, 发现水平距离减少了.
因此, 排队后, 排名不应该发生变化.

第二: 设排队后的第一个x坐标为a, 第二个为a + 1, 以此类推, 最后一个是a + N - 1
因为排名不发生变化, 因此, 排队前, 最左边的点对应的是a, 左边第二名对应的是a + 1, 以此类推, 最右边对应的是a + N - 1.
对x坐标进行排序.
水平距离之和等于abs(x0 - a) + abs(x1 - 1 - a) + abs(x2 - 2 - a) + … + abs(x(n-1) - (n - 1) - a)
令新的x坐标序列为(x0, x1 - 1, x2 - 2, ...., x(n - 1) - (n - 1)), 即原先xi变为了xi - i.
很明显, a取值为新的x坐标序列的中位值, 可以让水平距离之和最小化.

总结: 用了两次中位数, 其中水平方向的中位值计算稍微复杂一点点.

时间复杂度

O(N*log(N))

因为需要得到X坐标的排名, 因此, 必须得用一次排序.
即便中位值用到”快速选择”算法O(N), 并不会减少总体的时间复杂度O(N*log(N))
因此, 干脆中位数用排序的方法去求.

Python 代码

I = input
N = int(I())
X = []
Y = []
for i in range(N):
    x, y = map(int, I().split())
    X.append(x)
    Y.append(y)

ans = 0
Y.sort()
mid = Y[N // 2]
for y in Y:
    ans += abs(y - mid)

X.sort()
X2 = []
for i, x in enumerate(X):
    X2.append(x - i)
X2.sort()
mid = X2[N // 2]
for x in X2:
    ans += abs(x - mid)
print(ans)