题目理解

我们有 $2N$ 枚硬币，初始位置在 $(X_i, Y_i)$，目标是将它们移动到 $N \times 2$ 的矩形区域：$x$ 坐标从 $1$ 到 $N$，$y$ 坐标只有 $1$ 和 $2$。

每次移动只能到相邻格子（上下左右），求最小移动次数。

关键点：

• 网格无限大，但目标位置有限
• 移动过程中允许多个硬币在同一格子
• 最终每个目标格子恰好一枚硬币

关键观察

1. 曼哈顿距离的可分离性

在网格中，从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的曼哈顿距离为：

$$|x_1 - x_2| + |y_1 - y_2|$$

重要性质：$x$ 坐标的移动代价和 $y$ 坐标的移动代价可以分开计算。

2. 问题分解

我们可以将问题分解为两个独立的子问题：

1. $x$ 坐标分配：将 $2N$ 枚硬币分配到 $x$ 坐标 $1$ 到 $N$，每个 $x$ 坐标分配 $2$ 枚硬币
2. $y$ 坐标分配：对于每个 $x$ 坐标，将 $2$ 枚硬币分配到 $y$ 坐标 $1$ 和 $2$

3. 独立求解

对于 $x$ 坐标：

• 我们需要将 $2N$ 个 $X_i$ 值匹配到 $N$ 个目标 $x$ 坐标，每个目标位置匹配 $2$ 个硬币
• 最小化 $\sum |X_i - \text{target}_x|$

对于 $y$ 坐标：

• 对于每个固定的 $x$ 坐标，有 $2$ 枚硬币需要分配到 $y=1$ 和 $y=2$
• 最小化 $\sum |Y_i - \text{target}_y|$

算法设计

1. $x$ 坐标的优化

将所有的 $X_i$ 排序，设排序后为 $x_1 \leq x_2 \leq \cdots \leq x_{2N}$。

关键定理：最优分配是将排序后的 $x_i$ 按顺序两两分组，每组分配到同一个目标 $x$ 坐标。

更具体地说：

• 将 $x_1, x_2$ 分配到 $x=1$
• 将 $x_3, x_4$ 分配到 $x=2$
• ...
• 将 $x_{2N-1}, x_{2N}$ 分配到 $x=N$

证明思路：这相当于找 $2N$ 个数到 $N$ 个点（每个点容纳 $2$ 个数）的最小匹配，排序后顺序匹配是最优的。

$x$ 坐标的总代价为：

$$\sum_{i=1}^N (|x_{2i-1} - i| + |x_{2i} - i|)$$

2. $y$ 坐标的优化

对于每个目标 $x$ 坐标（即每组两枚硬币），我们需要将它们分配到 $y=1$ 和 $y=2$。

设这两枚硬币的原始 $y$ 坐标为 $y_a$ 和 $y_b$。

最优分配：

• 将 $y$ 值较小的硬币分配到 $y=1$
• 将 $y$ 值较大的硬币分配到 $y=2$

这样分配的代价为：

$$|y_{\min} - 1| + |y_{\max} - 2|$$

如果反过来分配，代价为：

$$|y_{\min} - 2| + |y_{\max} - 1| \geq |y_{\min} - 1| + |y_{\max} - 2| $$

因为 $y_{\min} \leq y_{\max}$，所以上述不等式成立。

3. 整合算法

1. 预处理：

   • 将所有硬币按 $X$ 坐标排序
   • 对于每组两个硬币，按 $Y$ 坐标排序

2. 计算总代价：

   • 对于 $i$ 从 $1$ 到 $N$：
     • $x$ 代价 $+= |X_{2i-1} - i| + |X_{2i} - i|$
     • 设 $y_1 = \min(Y_{2i-1}, Y_{2i})$, $y_2 = \max(Y_{2i-1}, Y_{2i})$
     • $y$ 代价 $+= |y_1 - 1| + |y_2 - 2|$

3. 总代价 = $x$ 代价 + $y$ 代价

正确性分析

1. $x$ 坐标分配的正确性

这是经典的"多对多"匹配问题。通过排序和顺序匹配，可以证明：

• 任何交叉匹配都会增加总距离
• 顺序匹配保证了全局最优性

2. $y$ 坐标分配的正确性

对于固定的两个 $y$ 坐标和两个目标位置：

• 如果 $y_a \leq y_b$，那么：
  • 分配 $(y_a \to 1, y_b \to 2)$ 的代价：$|y_a-1| + |y_b-2|$
  • 分配 $(y_a \to 2, y_b \to 1)$ 的代价：$|y_a-2| + |y_b-1|$
• 通过分类讨论可以证明前者总是更优

复杂度分析

• 排序：$O(N \log N)$
• 代价计算：$O(N)$
• 总复杂度：$O(N \log N)$，对于 $N \leq 10^5$ 可以接受

边界情况处理

1. 坐标范围：$X_i, Y_i$ 可能为负数，但绝对值函数处理自然
2. 大整数运算：结果可能很大，需要使用 long long
3. 排序稳定性：对于 $X$ 坐标相同的硬币，需要稳定排序或同时考虑 $Y$ 坐标

算法步骤总结

1. 读入数据：存储所有硬币的坐标
2. 按 $X$ 坐标排序：为 $x$ 坐标分配做准备
3. 分组处理：
   • 将排序后的硬币两两分组
   • 每组对应一个目标 $x$ 坐标
4. 计算代价：
   • 对每组计算 $x$ 坐标移动代价
   • 对每组计算 $y$ 坐标移动代价（按大小分配）
5. 输出结果：累加所有组的代价

总结

这道题的核心在于利用曼哈顿距离的可分离性和排序匹配的最优性：

1. 问题分解：将二维问题分解为两个一维问题
2. 排序匹配：通过排序实现 $x$ 坐标的最优分配
3. 贪心分配：对于 $y$ 坐标，按大小顺序匹配目标位置
4. 独立优化：两个维度的代价可以独立计算后相加

这种"维度分离 + 排序贪心"的思路在解决网格移动问题时非常有效，是算法竞赛中的重要技巧。