「Soldiers」士兵

形式化题目

给定平面上 $n$ 个整点 $(x_1, y_1), \dots, (x_n, y_n)$ ， $n \geqslant 1$ 。

一次移动可以把某个点的横坐标或纵坐标加一/减一，代价为 $1$ 。求最小总代价，使得移动后这 $n$ 个点恰好占据

\{(X, Y),\ (X+1, Y),\ \dots,\ (X+n-1, Y)\}

这 $n$ 个互不相同的格子，其中 $X, Y$ 可取任意整数。

形式化地，设 $\sigma$ 是士兵到格子编号的双射，要求

\min_{X,\ Y,\ \sigma}\ \sum_{i=1}^{n} \Big( \bigl|x_i - (X + \sigma(i))\bigr| + |y_i - Y| \Big)

正解

思路

朴素想法：直接枚举三个决策量——目标行 $Y$ 、目标段起点 $X$ 、以及士兵到格子的一一配对 $\sigma$ 。坐标范围 $|x_i|, |y_i| \leqslant 10000$ 把 $X, Y$ 的候选压缩到 $[-10000-n,\ 10000+n]$ 量级，但固定 $(X, Y)$ 后还有 $n!$ 种配对，总工作量是天文数字。瓶颈是决策变量太多，所以必须把 $\sigma$ 、 $X$ 、 $Y$ 逐个用解析结论消掉，而不是枚举。

关键观察一：两条坐标轴可以分开算。 看代价的组成： $y_i$ 只和 $Y$ 一起出现， $x_i$ 只和自己被分到的格子编号一起出现，两个方向之间没有交叉项；约束" $y$ 坐标相同"只约束 $Y$ ，" $x$ 坐标相邻"只约束 $X$ 与 $\sigma$ 。于是

\text{answer} = \underbrace{\min_{X,\sigma}\sum_i \bigl|x_i - (X+\sigma(i))\bigr|}_{f_x} \;+\; \underbrace{\min_{Y}\sum_i |y_i - Y|}_{f_y}

关键观察二： $y$ 方向取中位数。 $g(Y) = \sum_i |y_i - Y|$ 是凸的分段线性函数： $Y$ 每越过一个 $y_i$ ，斜率就增加 $2$ 。把 $y$ 升序排成 $y_{(0)} \le \dots \le y_{(n-1)}$ ，则在区间 $[y_{(k)}, y_{(k+1)}]$ 上斜率为 $2(k+1) - n$ ，它在 $k+1 \geqslant n/2$ 时由负转正，最小值就在中位数处取得：

f_y = \sum_i \bigl| y_i - y_{(\lfloor n/2 \rfloor)} \bigr|

关键观察三：固定 $X$ 后，最优配对是"排序后顺序发放"。 把 $x$ 升序排成 $x_{(0)} \le \dots \le x_{(n-1)}$ ，此时目标横坐标恰好是 $X, X+1, \dots, X+n-1$ 。若出现" $x$ 较小的士兵被分到较靠右的格子、 $x$ 较大的士兵被分到较靠左的格子"这样的逆序，那么把这两人的目标格子交换一下，一维绝对值的重排不等式保证总代价不增。这条不等式就是成本函数 $c(x,t)=|x-t|$ 的 Monge 性质： $a \leqslant b$ 、 $P \leqslant Q$ 时 $|a-P|+|b-Q| \leqslant |a-Q|+|b-P|$ ，按 $a, b$ 与 $P, Q$ 的四种位置关系分类拆开绝对值即可验证：

\bigl|x_{(i)} - (X+p)\bigr| + \bigl|x_{(j)} - (X+q)\bigr| \;\leqslant\; \bigl|x_{(i)} - (X+q)\bigr| + \bigl|x_{(j)} - (X+p)\bigr| \qquad (i<j,\ p<q)

反复消掉逆序，就得到"第 $i$ 小的人领第 $i$ 个格子"的顺序配对，配对方案 $\sigma$ 就此被消掉。

关键观察四： $x$ 方向也化归成中位数。 把顺序配对代回去：

f_x = \min_X \sum_{i=0}^{n-1} \bigl| x_{(i)} - (X+i) \bigr| = \min_X \sum_{i=0}^{n-1} \bigl| \underbrace{(x_{(i)} - i)}_{z_i} - X \bigr|

这和 $y$ 方向是同一个问题——“到一点的距离之和最小”，所以 $X$ 也取 $z_i = x_{(i)} - i$ 的中位数：

f_x = \sum_i \bigl| z_i - z_{(\lfloor n/2 \rfloor)} \bigr|

直观上， $z_i$ 是"假设整段的左端点放在 $0$ ，第 $i$ 个人还需要往左/往右平移多少"，取它的中位数就是把整段平移到左右两侧代价平衡的位置。

样例推演： $n = 5$ ，坐标为 $(1,2), (2,2), (1,3), (3,-2), (3,3)$ 。

先看 $y$ 方向： $y = [2,2,3,-2,3]$ 排序得 $[-2,2,2,3,3]$ ，下标 $5/2 = 2$ 的元素是中位数 $Y = 2$ 。

士兵 $y_i$	$-2$	$2$	$2$	$3$	$3$
$\lvert y_i - Y \rvert$ （ $Y=2$ ）	$4$	$0$	$0$	$1$	$1$

得到 $f_y = 4+0+0+1+1 = 6$ 。

再看 $x$ 方向： $x = [1,2,1,3,3]$ 排序得 $[1,1,2,3,3]$ ，减去下标得 $z = [1-0,\ 1-1,\ 2-2,\ 3-3,\ 3-4] = [1,0,0,0,-1]$ ，排序后 $[-1,0,0,0,1]$ ，中位数 $X = z_{(2)} = 0$ ， $f_x = 1+0+0+0+1 = 2$ 。

把两轴合起来看，最终的目标行是 $Y = 2$ ，目标横坐标是 $X+i = 0,1,2,3,4$ ，配对如下：

士兵（按 $x$ 升序）	$(1,2)$	$(1,3)$	$(2,2)$	$(3,-2)$	$(3,3)$
目标格子	$(0,2)$	$(1,2)$	$(2,2)$	$(3,2)$	$(4,2)$
$x$ 位移	$1$	$0$	$0$	$0$	$1$
$y$ 位移	$0$	$1$	$0$	$4$	$1$
小计	$1$	$1$	$0$	$4$	$2$

总计 $1+1+0+4+2 = 8$ ，恰好是 $f_x + f_y = 2 + 6$ ，与样例输出一致。

算法流程：对 $x$ 排序、错位成 $x_{(i)} - i$ 再排序取中位数求和；对 $y$ 排序取中位数求和；两者相加输出。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:52
# update_at: 2026-10-04 13:03

import sys


def median_cost(values: list[int]) -> int:
    """把这些数平移到同一个点，最小的总距离 = 各点到中位数的绝对距离之和。"""
    values.sort()
    median = values[len(values) // 2]
    return sum(abs(v - median) for v in values)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    pairs = [(next(data), next(data)) for _ in range(n)]  # 第 i 行的 (x[i], y[i])
    xs = [x for x, _ in pairs]
    ys = [y for _, y in pairs]

    # x 轴：目标是 n 个相邻格子 base, base+1, ..., base+n-1，排序后第 i 名士兵
    # 领第 i 个格子，因此把每人要走的偏移 i 提前扣掉，再对 base 取中位数。
    x_cost = median_cost([x - i for i, x in enumerate(sorted(xs))])
    # y 轴：全部站到同一行 Y，取 y 的中位数即可。
    print(x_cost + median_cost(ys))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:54
 * update_at: 2026-10-06 14:54
 */

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

typedef long long ll;

const int MAXN = 10005;

ll xs[MAXN]; // 士兵的 x 坐标，排序后按第 i 小的人领第 i 个格子错位
ll ys[MAXN]; // 士兵的 y 坐标

// 把这些数平移到同一个点，最小的总距离 = 各点到中位数的绝对距离之和。
// 数组按 a[1..n] 存储，调用时会被就地排序。
ll median_cost(ll a[], int n) {
    sort(a + 1, a + n + 1);
    ll median = a[n / 2 + 1]; // 下标从 1 开始的中位数位置
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        ll diff = a[i] - median;
        if (diff < 0) {
            diff = -diff;
        }
        total += diff;
    }
    return total;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", &xs[i], &ys[i]);
    }

    // x 轴：目标是 n 个相邻格子 X, X+1, ..., X+n-1。
    // 排序后第 i 小的人领第 i 个格子，于是把偏移 i-1 提前扣掉，再对 X 取中位数。
    sort(xs + 1, xs + n + 1);
    for (int i = 1; i <= n; i++) {
        xs[i] -= (i - 1);
    }
    ll x_cost = median_cost(xs, n);

    // y 轴：全部站到同一行 Y，取 y 的中位数即可。
    ll y_cost = median_cost(ys, n);

    printf("%lld\n", x_cost + y_cost);
    return 0;
}

median_cost 只回答一个问题——“把这些数平移到同一点，最小总距离是多少”，所以 $x$ 、 $y$ 两个方向共用它；x 轴的错位 x - i 必须在 sorted(xs) 的结果上做，因为只有排序之后"第 $i$ 小的人领第 $i$ 个格子"才成立。solve 只负责读入、两次调用和输出。

复杂度

时间：两次排序各 $O(n \log n)$ ，两次线性求和 $O(n)$ ，总计 $O(n \log n)$ 。 $n \leqslant 10000$ 时实测单组约 $0.02$ s，远低于 $1000$ ms 时限。
空间：两个长度 $n$ 的列表与两个 $O(n)$ 的切片，总计 $O(n)$ ；实测峰值内存约 $16$ MB，低于 $128$ MB。

总结

本题的解法可概括为三次"消元"，每一次都把一类决策变量从枚举里彻底删掉：

轴的解耦消掉二维耦合—— $x$ 与 $y$ 的代价可加，分别求最优即可；
重排不等式消掉配对方案 $\sigma$ ——排序后第 $i$ 小的人配第 $i$ 个格子最优；
中位数性质消掉连续量 $X, Y$ ——"到一点的距离之和最小"的解就是取中位数。

剩下要做的只有两遍排序。把"多决策量联合枚举"简化成"若干独立的凸函数取中位数"，是绝对值最优化问题的通用套路：凡是决策变量进入代价时只通过 $|v - \text{未知量}|$ 的形式，就应该先想能不能把它化成中位数。

图示解析

下图给出从题面到答案的完整主线：左侧是三个待定决策量，中间是消元后的两轴一维问题，右侧是最终的两遍排序实现。

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15输入 n 个点 (x_i, y_i)
   │  代价 = Σ|x_i - (X+σ(i))| + Σ|y_i - Y|     （x、y 之间没有交叉项）
   ▼
轴解耦：answer = f_x + f_y
   │
   ├── y 轴：固定 Y，代价 Σ|y_i - Y| 是凸函数，每越过一个点斜率 +2
   │          └─▶ Y = median(y)，fy = Σ|y_i - median(y)|
   │
   └── x 轴：固定 X，先用重排不等式消掉配对 σ
              ├─▶ σ：排序后第 i 小的人领第 i 个格子
              ├─▶ 代回得 Σ|(x_(i) - i) - X|，又变成"到一点距离和最小"
              └─▶ X = median(x_(i) - i)，fx = Σ|z_i - median(z)|
   │
   ▼
answer = fx + fy，两遍排序即可，复杂度 O(n log n)

这张图的关键在于中间那条分叉：题面里的三个决策量 $\sigma, X, Y$ 被分派到了两条互不干扰的轴上， $y$ 轴一步到位取中位数， $x$ 轴先消掉配对、再把带 $i$ 的偏移吸收进数据、最后同样落到中位数—— 两分支各自算出 $f_y$ 与 $f_x$ ，相加就是最终答案。

「Soldiers」 士兵

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析