题意

有 $N$ 个士兵，每个士兵开始站的坐标是 $(x，y)$，现在使得将 $N$ 个士兵站在同一个水平线（即所有士兵的 $y$ 坐标相同）并且 $x$ 坐标相邻，每个士兵每次可以移动一个位置（分别在 $x$ 和 $y$ 方向移动）。求出最少的移动步数。

解题思路

这是一个最优化问题，可以使用中位数计算来解决。$x$ 方向和 $y$ 方向可以分别来考虑。

$y$ 方向就是一个简单的中位数计算。

$x$ 方向是坐标相邻，可以先将 $x$ 位置排序，然后往中间靠，也是一个中位数计算问题。$x$ 方向分别移动到 $a+i$ 的位置，那么士兵就相邻了，即 $x[i]=a+i$，那么 $x[i]-i=a$。用中位数来算的话，首先将 $x$ 方向进行排序，然后让 $x[i]=x[i]-i$，再次排序后求中位数即可。## 题意 有N个士兵，每个士兵开始站的坐标是（x，y），现在使得将N个士兵站在同一个水平线（即所有士兵的y坐标相同）并且x坐标相邻，每个士兵每次可以移动一个位置（分别在x和y方向移动）。求出最少的移动步数。

标程

#include <iostream>
#include <algorithm>
#include <cstdlib> 

using namespace std;

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

int main() {
    int n;

    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }

        sort(x, x + n);
        for (int i = 0; i < n; i++) {
            x[i] -= i;
        }
        sort(x, x + n);
        sort(y, y + n);

        int ans = 0, x_median, y_median;
        if (n % 2 == 1) {
            x_median = x[n / 2];
            y_median = y[n / 2];
        } else {
            x_median = (x[n / 2 - 1] + x[n / 2]) / 2;
            y_median = (y[n / 2 - 1] + y[n / 2]) / 2;
        }

        for (int i = 0; i < n; i++) {
            ans += abs(x_median - x[i]) + abs(y_median - y[i]);
        }

        cout << ans << endl;
    }

    return 0;
}