当前位置: 代码迷 >> 综合 >> poj 1723 SOLDIERS 中位数
  详细解决方案

poj 1723 SOLDIERS 中位数

热度:34   发布时间:2024-01-19 05:54:05.0

题意:

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


  相关解决方案