在平面直角坐标系上，存在n个整点，第i个点的坐标记作((x_i,y_i))，每个点可以选择向上下左或右移动一个单位长度，移动时点不能重叠，请问将所有排成一条水平直线的最少移动步数，(nleq 10000)。
解
首先，平面直角坐标系上的整点问题可以看做网格图问题，而网格图中有一种处理方法，就是行列独立，显然，我们可以先将x轴方向上排成一排，然后再将y方向的坐标移到同一坐标。
而x轴方向排成一排，不妨按x坐标排序，记第一个点移到(x_p)，显然第二个点移到(x_p+1),以此类推，于是x轴方向上的答案为
(sum_{i=1}^n|x_i-(x_p+i-1)|=sum_{i=1}^n|x_i-i+1-x_p|)，此时，如果将设(x'_i=x_i-i+1)，那么问题就变成求解(sum_{i=1}^n|x'_i-x_p|)的最小值，显然将(x')排序后，取中位数即可。
对于y方向上的移动，就更加简单了，我们只要去一个(y_p)，最小化(sum_{i=1}^n|y_i-y_p|)，同样按y轴坐标排序后取中位数即可。
然后就可以在(nlog(n))解决问题。
参考代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define il inline
#define ri register
#define Size 10050
using namespace std;
int x[Size],y[Size];
il void read(int&);
template<class free>
il free Abs(free);
int main(){
int n;read(n);
for(int i(1);i<=n;++i)
read(x[i]),read(y[i]);
sort(x+1,x+n+1),sort(y+1,y+n+1);
for(int i(1);i<=n;++i)x[i]-=i-1;
sort(x+1,x+n+1);int mx(x[1+n>>1]),my(y[1+n>>1]),ans(0);
for(int i(1);i<=n;++i)ans+=Abs(mx-x[i])+Abs(my-y[i]);
printf("%d",ans);
return 0;
}
template<class free>
il free Abs(free x){
return x<0?-x:x;
}
il void read(int &x){
x^=x;ri char c;while(c=getchar(),c==' '||c=='
'||c=='
');
ri bool check(false);if(c=='-')check|=true,c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
if(check)x=-x;
}