题意:
给n个士兵的坐标,要把他们移动到水平且相邻的一行,求最小步数。
分析:
中位数法,y方向易求,x方向x0->n+i与x0-i->n是对应的,故也可以转换成y方向的情况。
代码:
//poj 1723
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
const int maxN=10024;
int x[maxN],y[maxN];
int cmp(int a,int b)
{return a<b;
}
int main()
{int i,n,ans=0;scanf("%d",&n);for(i=0;i<n;++i){scanf("%d%d",&x[i],&y[i]);}sort(x,x+n);for(i=0;i<n;++i) x[i]-=i;sort(x,x+n);sort(y,y+n);for(i=0;i<n;++i){ans+=abs(x[i]-x[n/2]);ans+=abs(y[i]-y[n/2]);}printf("%d",ans);return 0;
}