题目概述
在一个划分成网格的操场上， n个士兵散乱地站在网格点上。由整数 坐标 (x,y) 表示。士兵们可以沿网格边上、下左右移动一步，但在同时刻任一网格点上只能有名士兵。按照军官的命令，们要整齐地列成个水平队列，即排成 队列，即排成 (x,y),(x+1,y), …,(x+n -1,y) 。如何选择 x 和y的值才能使 士兵们以最少的总移动步数排成一列。
解题思路
虽然士兵的坐标分横纵，但仔细想想，其实可以分开来算。
我们可以先排序，并求出y轴坐标的中位数。
对于x轴，可以先假设将士兵们排在x=0,1,2…(n-1)的位置(按横坐标顺序排列)，记录下每个士兵需要移动的长度， 排序，再找到它们的中位数cmid。则x轴上需要移动的总长度为Sx=|x1-cmid|+|x2-cmid+1|+…+|xn-cmid+n-1|。
对于y轴，想要排在同一行，设该行纵坐标为p，则y轴上需要移动的总长度为Sy=|p-y1|+|p-y2|+…+|p-yn|。当p为所有x轴坐标的中位数时，总长度最小。
最后将Sx与Sy相加，输出结果。
时间复杂度：O(nlog n)
空间复杂度：O(n)
源程序
var a,b,c,d:array[1..10002]of longint; i,n,t,ans,mid:longint; procedure ms(s,m,t:longint); var f:array[1..10002]of longint; i,j,k,p:longint; begin i:=s;j:=m+1;k:=s-1; while (i<=m)and(j<=t)do begin if a[i]<a[j] then begin inc(k); f[k]:=a[i]; inc(i); end else begin inc(k); f[k]:=a[j]; inc(j); end; end; while i<=m do begin inc(k);f[k]:=a[i];inc(i);end; while j<=t do begin inc(k);f[k]:=a[j];inc(j);end; for p:=s to t do a[p]:=f[p]; end; procedure ms2(l,r:longint); var m:longint; begin if l>=r then exit; m:=(l+r) div 2; ms2(l,m); ms2(m+1,r); ms(l,m,r); end; begin readln(n); for i:=1 to n do readln(b[i],a[i]); ms2(1,n); ans:=0; mid:=a[(n div 2)+1]; for i:=1 to n do ans:=ans+abs(a[i]-mid); a:=b; ms2(1,n); b:=a; for i:=1 to n do c[i]:=b[i]-i+1; a:=c; ms2(1,n); c:=a; mid:=c[(n div 2)+1]; for i:=1 to n do ans:=ans+abs(b[i]-mid-i+1); write(ans); end.
