题目链接

算法竞赛进阶指南-36.士兵

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

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

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

输出样例：

8

Method : 排序 + 中位数

P1889 士兵站队

首先把二维拆开来看，看成两个一维问题。

y坐标相同=>货仓选址问题， 选择$y$的中位数;

x坐标相邻=>货仓选址问题变形，选择$xi - i$的中位数。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 1e4 + 7;

vector<PII> points;
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int x, y;
        scanf("%d %d", &x, &y);
        points.push_back({x, y});
    }
    
    long long cost = 0;
    
    // 计算y的cost
    sort(points.begin(), points.end(), [](const PII& a, const PII& b) {
        return a.second < b.second;
    });
    for (int i = 0; i < n; i ++) {
        cost += abs(points[i].second - points[n / 2].second);
    }
    
    // 计算x的cost
    sort(points.begin(), points.end(), [](const PII& a, const PII& b) {
        return a.first < b.first;
    });
    for (int i = 0; i < n; i ++) {
        points[i].first -= i;
    }
    sort(points.begin(), points.end(), [](const PII& a, const PII& b) {
        return a.first < b.first;
    });
    
    for (int i = 0; i < n; i ++) {
        cost += abs(points[i].first - points[n / 2].first);
    }
    
    cout << cost << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n\log n)}$，其中$nlog n$为sort排序的时间复杂度。

• 空间复杂度：${O(n)}$，空间开销主要在$points$数组上。