货仓选址问题的变种，看了一些题解，觉得对于新手来说有点抽象（特别是$x$方向上的推导），于是写得稍微详细一点，如果觉得好不妨点个赞（x

算法

排序，中位数

本题的难度在于分析出这是一个货仓选址问题，一旦看出来，编程难度不大（没有）。
与七夕祭类似，本题需要解决两个维度上的问题。一般来说，要么两者是有关联的，要么可以独立来分析，前者往往稍微难一点。此处，我们不难看出，$x$方向上的变化并不会影响到$y$方向上（和七夕祭也是一样的），故而我们可以独立地分析两者。
首先是如何处理题目中的输入数据，我们可以将所有列\行看成数轴上的点（我一开始的抽象是，统计各个位置上的点数，但这样实际上是等效的，也就是一个加权的区别）。

$y$轴情况

题目中要求，最终所有的士兵都在同一个$y$坐标下，这实际上就等效于找到一个位置$k$，使得
$\sum_{i=1}^{n}|y_i-k|$最小，此处$n$为总的士兵数。
看到式子，就不难想到这是一个货仓选址的模型了。这个模型告诉我们，对于上面的绝对值形式的式子，我们取$k$为数列$y_{1,2\cdots,n}$的中位数时取得最小值（初中的一个结论）。体现在编程上，就是排序。

$x$轴情况

接下来看$x$轴的情况。
题目中要求，最终所有的点$x$坐标相邻，也就是最终所有的$x$坐标是递增的，那么从哪里开始递增呢？
我们可以仿效$y$轴的处理方式，假设最终选取的开始递增的位置为$k$，那么最终位于第$i$个位置的点就应该位于$k+i-1$位置上（为了形式的简单，我们可以令$k\prime=k-1$）。
问题来了，每个点最终处于序列中哪一个位置呢？一个基本的想法是，按照升序排。如果不按照升序，那么在原始的数列中就有点对逆序，必然会多移动一段路径，故而我们需要先对$x_{1,2,\cdots,n}$数列排序。对排序后的数列而言，我们所要求的的实际上就是：
$\sum_{i=1}^{n}|x_i-(k\prime+i)|$最小，此处$n$为总的士兵数。
形式与$y$轴情况是类似的，我们可以将$x_i-i$看做一个整体$x\prime_i$，问题就转化为了对其的货仓问题。

时间复杂度

所有的时间复杂度都在排序上，故而是$O(nlogn)$。

参考文献

无

C++ 代码

#include <bits/stdc++.h>
#define oj
using namespace std;

const int maxn = 10000 + 10;
int xx[maxn], yy[maxn];//用来存储x与y方向上的点的位置（一种离散化的操作，在文中提到，我一开始的操作是建立一个坐标到数值的映射，但实际上最终还是要进行离散化，不如一开始就离散话）

int main(){
    #ifndef oj
    freopen("data.in", "r", stdin);
    freopen("oj.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        xx[i] = a, yy[i] = b;
    }

    int ans = 0;
    sort(xx + 1, xx + 1 + n);
    sort(yy + 1, yy + 1 + n);//排序是必要的
    for (int i=1; i<=n; i++) {
        xx[i] -= i;
    }
    sort(xx + 1, xx + n + 1);
    int mid1 = (n & 1) ? xx[(n + 1) >> 1] : xx[n >> 1],
        mid2 = (n & 1) ? yy[(n + 1) >> 1] : yy[n >> 1];//找中位数
    for (int i=1; i<=n; i++) {
        ans += abs(xx[i] - mid1) + abs(yy[i] - mid2);//货仓选址
    }
    cout << ans << endl;
    return 0;
}