POJ1723 Soldiers

题意

$n\times n$ 的格点中站了 $n$ 个人，要让他们站在一排，求最少的移动次数。

$n\le 100000$ 。

题解

选择第几排

显然是取所有人 $y$ 坐标的中位数最优。

移动到相应位置

显然，按照 $x$ 的坐标顺序安排这一排内的顺序是最优的，所以先对 $x_i$ 进行第一次排序。

但这样还是需要移动到不同位置，于是处理 $x_i-i$ ，这样就相当于移动到同一位置了，取中位数即可。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,ans,x[10005],y[10005];

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) x[i]=read(),y[i]=read();
    ll mid=(n>>1)+1;
    sort(y+1,y+n+1);
    for (ll i=1;i<=n;i++) ans+=abs(y[mid]-y[i]);
    sort(x+1,x+n+1);
    for (ll i=1;i<=n;i++) x[i]-=i;
    sort(x+1,x+n+1);
    for (ll i=1;i<=n;i++) ans+=abs(x[mid]-x[i]);
    return !printf("%lld",ans);
}