题目描述

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点用整数坐标(x,y)表示。士兵们可以沿网格边往上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x和y的值才能使士兵们以最少的总移动步数排成一行。

编程计算使所有士兵排成一行需要的最少移动步数。

输入格式

第1行是士兵数n，1≤n≤10000。接下来n行是士兵的初始位置，每行有2个整数x和y，-10000≤x，y≤10000。

输出格式

一个数据，即士兵排成一行需要的最少移动步数。

题目分析

可以发现，士兵移动可以分为x方向，和y方向两种互不影响的部分。
首先讨论y方向：
只观察y方向，可以认为士兵都在同一列，并向该列中心点移动。猜想该中心点位置为y坐标的平均数或中位数，通过举反例的方式可以排除平均数的可能（2, 4，-6），因此为y坐标的中位数y0。
士兵y方向上走的步数为

for(int i=1;i<=n/2;i++)
    {
        ymile+=y[n-i+1]-y[i];
    }

再讨论x方向：
只观察x方向，士兵可以认为士兵都在同一排。首先对士兵x位置进行从小到大排序，为每位士兵编号x1,x2,x3···设士兵排成一排时左起第一个人的位置为x0，则第二个人位置为x0+1，第三个人位置为x0+2，以此类推，第i个人位置为x0+(i-1)。则士兵在x方向上需要移动的步数为 |x1-x0|+|x2-x0-1|+|x3-x0-2|+···进行转化后|x1-x0|+|(x2-1)-x0|+|(x3-2)-x0|+···，类比y方向可知，x0是（xi-i+1）数列的中位数。

for(int i=1;i<=n;i++)
    {
        x[i]=x[i]-i+1;
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=n/2;i++)
    {
        xmile+=x[n-i+1]-x[i];
    }

完全代码

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int x[10010],y[10010];
    int px,py;
    int ymile=0,xmile=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {    
        scanf("%d%d",&x[i],&y[i]);
    }
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);
    for(int i=1;i<=n/2;i++)
    {
        ymile+=y[n-i+1]-y[i];
    }
    for(int i=1;i<=n;i++)
    {
        x[i]=x[i]-i+1;
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=n/2;i++)
    {
        xmile+=x[n-i+1]-x[i];
    }
    printf("%d",xmile+ymile);
    return 0;
}