题解 P1889 【士兵站队】
P1889 士兵站队 题解
好多Dalao写的我没看明白，那么我就自己写一篇吧
附送题目链接：P1889士兵站队
那么我就不多解释题目了；
对于输入士兵的坐标：
纵坐标处理
我们先看纵坐标（其实是纵坐标比较简单）
- 我们假设士兵要移动到的目标纵坐标为m；
那么我们可以推导出一大堆的东西： 士兵在垂直于x轴方向上的移动距离为：
|y1-m|+|y2-m|+|y3-m|+……+|yn-1-m|+|yn-m|那么m取什么值最小呢？显而易见，就是y1~yn序列的中位数，实现代码如下：
int rey;
sort(y+1,y+n+1);
if(!n%2) rey=(y[n/2]+y[n/2+1])/2;
//!n%2意为 n%2 =0(在if语句里写2个'=')，即 n%2 为假
else rey=y[n/2+1];
横坐标处理
现在到了x麻烦了，因为有可能两位士兵的横坐标是相同的！而纵坐标的相同对于计算并没有影响！
~到这里实在不懂的要自己画下图了~
那接着怎么办？
依旧假设~ ，我们假设第一位士兵站的位置是k，因为x从x1开始，那么我们假设成起始位置为k+1吧(不懂接着看完你就懂了）
那么：第二位士兵的位置是 k+2，接着是k+3,k+4,……,k+n;
所以，士兵横向(即平行于y轴方向)移动的距离为：
|x1-(k+1)|+|x2-(k+2)|+|x3-(k+3)|+……+|x(n-1)-(k+n-1)|+|xn-(k+n)|那么k取何值会使上式最小？我们不妨变形一下：
|(x1-1)-k)|+|(x2-2)-k)|+|(x3-3)-k)|+……+|(x(n-1)-(n-1))-k)|+|(xn-n)-k)|
//x(n-1)中 n-1 是x的下标emmmm……于是又是中位数了！
结论：我们只需要取 k=xi-i的中位数就好了！
代码很容易实现，同纵坐标的的处理，先排序，但这次我们要将xi-i之后再次排序，再取中位数；
代码实现如下：
int rex;
sort(x+1,x+n+1);
for(int i=1;i<=n;i++) x[i]-=i;
sort(x+1,x+n+1);
//处理完还要再排序；
if(!n%2) rex=(x[n/2]+x[n/2+1])/2;
//同上；
else rex=x[n/2+1];到此，核心的部分就结束了
然后程序就over了；
完整代码实现：
//认真看 杜绝抄袭
#include<cstdio>
#include<algorithm>
//使用 sort 排序函数 调用算法库;
#include<cmath>
//使用 abs 绝对值函数 调用数学库;
using namespace std;
int n,x[10005],y[10005],ans=0,rex,rey;
//输入士兵数n，x数组储存士兵横坐标，y数组储存士兵纵坐标;
//ans统计步数和，rex记平行于x轴(即横方向)的中位数，rey记行于y轴(即纵方向)的中位数;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",x+i,y+i);
//输入完毕
sort(x+1,x+n+1); sort(y+1,y+n+1);
//无论如何都要先排序,sort调用'algorithm'(算法)库;
for(int i=1;i<=n;i++) x[i]-=i;
sort(x+1,x+n+1);
//处理完横坐标还要再排序一次;
if(!n%2)
//人数n为偶数;
//相当于'if(n%2==0)';
{
rex=(x[n/2]+x[n/2+1])/2;
rey=(y[n/2]+y[n/2+1])/2;
//数学知识不解释了，自己多算;
}
else//否则为奇数
{
rex=x[n/2+1];
rey=y[n/2+1];
}
for(int i=1;i<=n;i++) ans+=abs(x[i]-rex)+abs(y[i]-rey);
//abs为绝对值函数，调用'cmath'(数学)库;
printf("%d",ans);
//输出完毕,程序结束;
return 0;//这个千万不能漏！
}