题目描述

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

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

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

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

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

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

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

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

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

数据范围
$1≤N≤10000$
$−10000≤x[i],y[i]≤10000$

样例

输入样例：
5
1 2
2 2
1 3
3 -2
3 3
输出样例：
8

两组中位数+排序+离散化

这道题目其实就是让我们找到$x$坐标中,最中间的坐标$x$,$y$坐标中,最中间的坐标$y$,也就是中位数.

我们发现x和y坐标是要分开考虑的,因为题目中没有说找一个点,而是找到一个区间.上面题目描述中已经标黑了.

至于为什么呢,我们可以这么思考,就是说,因为我们目标的坐标$x$和坐标$y$是要让我们求出来的,记住不是$(x,y)$一对坐标,是两个单独的坐标.

我们发现,中位数的性质,就是其余所有的点到中位数的路程是最短的,所以说我们要找中位数,还要记住这些点,可能x坐标相同,y坐标不同,我们要离散化.

感谢@byene0923大佬指出下面的代码一个错误

这里的 x[ i ] - i,并不是离散化....
对x进行排序后,要求使得士兵全部相邻的最小移动次数.那么在移动前和移动后，士兵的相对位置是不变的.
举例来说,记add为移动后的最左端的士兵的前一位置
x[ 1 ] -> add + 1;
x[ 2 ] -> add + 2;
…
x[ n ] -> add + n;
转换一下
x[ 1 ] - 1 -> add;
x[ 2 ] - 2 -> add;
…
x[ n ] - n -> add;
这就转化为了跟y轴一样的问题了

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir(a,b,c) for (ll a=b;a<=c;a++)//宏定义for循环
const int N=10050;
ll x[N],y[N],n,x_mid,y_mid,ans=0;
int main() 
{
    ios::sync_with_stdio(false);
    cin>>n;
    fir(i,1,n)
        cin>>x[i]>>y[i];
    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    fir(i,1,n)
        x[i]-=i;
    sort(x+1,x+1+n);
    x_mid=x[(n+1)>>1];//x坐标的中位数
    y_mid=y[(n+1)>>1];//y坐标的中位数
    fir(i,1,n)
    {
        ans+=abs(x[i]-x_mid);
        ans+=abs(y[i]-y_mid);
    }
    cout<<ans;
    return 0;
}