士兵站位问题soliders_综合

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。计算使所有士兵排成一行需要的最少移动步数。

输入

第1 行是油井数n，1< =n< =10000。接下来n 行是油井的位置，每行2个整数x和y，-10000< =x，y< =10000。

输出

第1 行中的数是士兵排成一行需要的最少移动步数。

样例输入

样例输出

解题思路：这道题其实跟邮局选址问题和油管问题很像，需要注意的是x方向的最近距离，士兵需要按照顺序站位，因此第一个士兵的移动距离是|x1-x|,第二个士兵的移动距离是|x2-x-1|，即到最优点x的邻近点的位置，因此总距离为|x1-x|+|x2-x-1|+|x3-x-2|+...+|xn-n-n+1|,因此可求得最优点的x坐标为x1,x2-1...xn-n+1的中间值。

代码如下：

#include<iostream>
#include <cstdio>  
#include <cstring>  
#include <cmath> 
#include<algorithm>
using namespace std;
#define N 10005
struct Soldier
{int x;int y;
}soldier[N],b[N];
int n,sum=0;
bool cmpx(const Soldier& a,const Soldier& b)
{return a.x<b.x;
}bool cmpy(const Soldier& a,const Soldier& b)
{return a.y<b.y;
}
bool cmpxy(int a,int b)
{return a<b;
}int main()
{int px=0,py=0;cin>>n;for(int i=0;i<n;i++){cin>>soldier[i].x>>soldier[i].y;}memcpy(b,soldier,sizeof(b));sort(soldier,soldier+n,cmpy);py=soldier[n/2].y;sort(b,b+n,cmpx);for(int i=0;i<n;i++){b[i].x=b[i].x-i;}sort(b,b+n,cmpx);px=b[n/2].x;sort(soldier,soldier+n,cmpx);for(int i=0;i<n;i++){sum+=abs(soldier[i].x-px-i)+abs(soldier[i].y-py);}cout<<sum<<endl;return 0;
}