题目描述

在一个划分成网格的操场上,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;
}