首页 > 代码库 > poj 1723 SOLDIERS 中位数

poj 1723 SOLDIERS 中位数

题意:

给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;	
} 


poj 1723 SOLDIERS 中位数