题目地址：

https://www.acwing.com/problem/content/description/125/

格格兰郡的$N$名士兵随机散落在全郡各地。格格兰郡中的位置由一对$(x,y)$整数坐标表示。士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的$x$或$y$坐标也将加$1$或减$1$）。现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的$y$坐标相同并且$x$坐标相邻。请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。需注意，两个或多个士兵不能占据同一个位置。

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

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

数据范围：
$1\le N\le 10000$
$-10000\le x[i],y[i]\le 10000$

$y$轴方向上，问题与https://blog.csdn.net/qq_46105170/article/details/114134378一样，直接取最终位置为中位数即可。对于$x$轴方向，设$x_i,i=0,1,...,n$已经排好序，设$a,a+1,...,a+n-1$是他们最终所在位置的$x$下标，显然$x_0$这个人要去$a$位置，$x_1$这个人要去$a+1$这个位置，以此类推（首先，这$n$个人是可以“不相撞”地走到这些位置的，例如我们直接让$x_0$走去$a$，如果途中$x_0$要碰到别人，那么可以将这个过程想象为$x_0$把这个人挤到下一个位置，以此类推，所以本质上对于任意的$a$我们都有办法让这些人归位，并且每个人的走法不会含回头路，且可以看成相互独立不影响）。那么$x$方向上的总步数为：$$\sum _{k=1}^n|x_k-(a+k-1)|=\sum _{k=1}^n|(x_k-k+1)-a|$$将$(x_k-k+1)$看成一个整体，则问题又变为https://blog.csdn.net/qq_46105170/article/details/114134378一样。代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
int n;
int x[N], y[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
  int res = 0;
  sort(y + 1, y + 1 + n);
  int ymed = y[n + 1 >> 1];
  for (int i = 1; i <= n; i++) res += abs(y[i] - ymed);
  sort(x + 1, x + 1 + n);
  for (int i = 1; i <= n; i++) x[i] -= i - 1;
  sort(x + 1, x + 1 + n);
  int xmed = x[n + 1 >> 1];
  for (int i = 1; i <= n; i++) res += abs(x[i] - xmed);
  printf("%d\n", res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度$O(n\log n)$，空间$O(1)$。