士兵移动问题

题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

8

输入输出样例 #2

输入 #2

3
0 0
1 0
2 0

输出 #2

2

限制条件

• $1 \le N \le 10000$
• $-10000 \le x[i], y[i] \le 10000$

样例解释 #1

士兵坐标：

1. $(1, 2)$
2. $(2, 2)$
3. $(1, 3)$
4. $(3, -2)$
5. $(3, 3)$

目标：所有士兵最终排成一条水平线，$y$ 坐标相同，$x$ 坐标相邻。

步骤分析

1. $y$ 坐标统一 首先需要确定最终的水平线位置（$y$ 坐标）。这是一个货仓选址问题，最优解是取所有 $y$ 坐标的中位数。

将 $y$ 坐标排序：$[-2, 2, 2, 3, 3]$ 中位数是 $2$，所以最终所有士兵的 $y$ 坐标应为 $2$。

$y$ 方向移动距离：

• 士兵1：$|2-2| = 0$
• 士兵2：$|2-2| = 0$
• 士兵3：$|3-2| = 1$
• 士兵4：$|-2-2| = 4$
• 士兵5：$|3-2| = 1$

$y$ 方向总移动距离：$0+0+1+4+1 = 6$

2. $x$ 坐标排列 所有士兵在 $x$ 轴上排列成相邻位置。

将 $x$ 坐标排序：$[1, 1, 2, 3, 3]$ 假设最终位置为 $[x_0, x_0+1, x_0+2, x_0+3, x_0+4]$

这是一个货仓选址问题的变种：要最小化 $\sum_{i=0}^{4} |(x_0+i) - x_i'|$，其中 $x_i'$ 是排序后的 $x$ 坐标。

最优解是让 $x_0$ 满足 $x_0 = x_i' - i$ 的中位数。

计算 $x_i' - i$：

• 士兵1：$1 - 0 = 1$
• 士兵2：$1 - 1 = 0$
• 士兵3：$2 - 2 = 0$
• 士兵4：$3 - 3 = 0$
• 士兵5：$3 - 4 = -1$

排序：$[-1, 0, 0, 0, 1]$ 中位数是 $0$，所以 $x_0 = 0$

最终 $x$ 坐标：$[0, 1, 2, 3, 4]$

$x$ 方向移动距离：

• 士兵1：$|1-0| = 1$
• 士兵2：$|2-1| = 1$
• 士兵3：$|1-2| = 1$
• 士兵4：$|3-3| = 0$
• 士兵5：$|3-4| = 1$

$x$ 方向总移动距离：$1+1+1+0+1 = 4$

总移动距离：$6 + 4 = 10$（但题目答案是 8，需要检查）

让我重新计算，可能我理解有误。

实际上，对于 $x$ 坐标，我们需要先排序 $x$ 坐标：$[1, 1, 2, 3, 3]$ 然后让这些 $x$ 值对应到连续的整数位置。

设最终位置为 $[k, k+1, k+2, k+3, k+4]$，其中 $k$ 是整数。

最小化 $\sum_{i=0}^{4} |x_i - (k+i)|$，其中 $x_i$ 是排序后的 $x$ 坐标。

令 $b_i = x_i - i$，则问题转化为最小化 $\sum_{i=0}^{4} |b_i - k|$。

这是一个货仓选址问题，最优 $k$ 是 $b_i$ 的中位数。

计算 $b_i$：

• $b_0 = 1 - 0 = 1$
• $b_1 = 1 - 1 = 0$
• $b_2 = 2 - 2 = 0$
• $b_3 = 3 - 3 = 0$
• $b_4 = 3 - 4 = -1$

$b_i$ 排序：$[-1, 0, 0, 0, 1]$ 中位数是 $0$，所以 $k = 0$

最终位置：$[0, 1, 2, 3, 4]$

移动距离：

• 原始 $x=1$ → 位置 0：距离 1
• 原始 $x=1$ → 位置 1：距离 0
• 原始 $x=2$ → 位置 2：距离 0
• 原始 $x=3$ → 位置 3：距离 0
• 原始 $x=3$ → 位置 4：距离 1

$x$ 方向总移动：$1+0+0+0+1 = 2$

加上 $y$ 方向移动 6，总移动 8。

所以答案是 8。