士兵

格格兰郡的 $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$ 轴很好处理，就是 货仓选址。

对于 $x$ 轴，有题目可得所有士兵的 $x$ 轴相邻，假设第一位士兵的左边一格的 $x$ 轴为 $a$，

第一位士兵的坐标为 $a + 1$

第二位士兵的坐标为 $a + 2$

第三位士兵的坐标为 $a + 3$

….

最后一名士兵的坐标为 $a + n$

对于每个 $i$ ，这个结果就可以简化为

第 $i$ 位士兵的坐标为 $a + i$

对于每个士兵的原坐标 $b_i$ ，我们要将 $b_i$ 移动到 $a + i$ 就相当于要将 $b_i - i$ 移动到 $a$

所有不同点移动到相同点，这就是 $y$ 轴上的等价问题，处理后排序找中间值即可

#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 10005;
int x[N], y[N];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &x[i], &y[i]);
	}
	
	std::sort(y + 1, y + 1 + n);
	
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += std::abs(y[i] - y[(1 + n) >> 1]);
	}
	
	std::sort(x + 1, x + 1 + n);
	for (int i = 1; i <= n; i++) x[i] = x[i] - i;
	std::sort(x + 1, x + 1 + n);
	for (int i = 1; i <= n; i++) {
	    ans += std::abs(x[i] - x[(1 + n) >> 1]);
	}
	
	printf("%d\n", ans);
	return 0;
}