题目描述

格格兰郡的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和y,我们是可以分开计算的,因为在x或y方向上的移动是互不影响的
而且不管是x还是y,都至少会有一个不移动,因为我们只需要相对位置的改变,每个都移动了的话显然不会是最优方案
那么我们假设排序后不移动的点序号为k

对于y方向,移动步数为$\sum_{i=1}^{n} |y[i]-y[k]|$.设小于y[k]的点有p个,大于y[k]的点有q个.那么当y[k]减少1,步数变为$\sum_{i=1}^{n}|y[i]-y[k]|+q-p$;
同理,当y[k]增加1,步数变为$\sum_{i=1}^{n} |y[i]-y[k]|+p-q$.
所以当y[k]为中位数时得到最优解

对于x方向,为了获得最优方案,移动前移动后的顺序应该不变.且对于在x方向重合的点,由于排序时它们获得了不同的序号,可以视为这一堆相等的点已经排成一列了
移动步数为$\sum_{i=1}^{n} |x[i]-x[k]|-|i-k|=\sum_{i=1}^{n}|(x[i]-i)-(x[k]-k)|$
(可以看作将这些点往选定的点按序凑近,建议画图理解)
与上同理,将x[i]-i视为一个新的整体进行排序,取x[k]-k为其中的中位数可得到最优解

代码:

#include <cstdio>
#include <algorithm>
const int maxn=10000+10;
using std::sort;
using std::abs;
int x[maxn],y[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    sort(x+1, x+1+n);
    sort(y+1, y+1+n);
    int ans=0;
    for (int i=1;i<=n;i++)
        x[i]-=i;
    sort(x+1, x+1+n);
    for (int i=1,k=n+1>>1;i<=n;i++)
        ans+=abs(x[i]-x[k])+abs(y[i]-y[k]);
    printf("%d\n",ans);
    return 0;
}