算法竞赛进阶指南：士兵（Python）

题目描述：

格格兰郡的 N 名士兵随机散落在全郡各地。

格格兰郡中的位置由一对 (x,y)整数坐标表示。

士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 x 或 y 坐标也将加 1 或减 1）。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 y 坐标相同并且 x 坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

需注意，两个或多个士兵不能占据同一个位置。

输入格式

第一行输入整数 N，代表士兵的数量。

接下来的 N 行，每行输入两个整数 x 和 y，分别代表一个士兵所在位置的 x 坐标和 y 坐标，第 i 行即为第 i 个士兵的坐标 (x[i],y[i])。

输出格式

输出一个整数，代表所有士兵的总移动次数的最小值。

数据范围

1≤N≤10000,
−10000≤x[i],y[i]≤10000

输入样例：

5
1 2
2 2
1 3
3 -2
3 3

输出样例：

8

解题思路： 

排序 + 中位数
根据距离公式, 容易发现水平距离之和和垂直距离之和可以独立计算.
分别让水平距离之和最小化, 垂直距离之和最小化, 就可以得到距离之和最小化.
垂直距离之和非常容易, 排队后的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))
因此, 干脆中位数用排序的方法去求.

Python3代码： 

 
N = int(input())
X = [] ; Y = []
 
for i in range(N) :
    x,y = map(int,input().split())
    X.append(x) ; Y.append(y)
    
ans = 0
Y.sort()
mid_Y = Y[N//2]
X.sort()
X2 = []
for i in range(N) : X2.append(X[i] - i)
X2.sort()
mid_X = X2[N//2]
 
for i in range(N) :
    ans += abs(X2[i] - mid_X) + abs(Y[i] - mid_Y)
    
print(ans)