-----------------------------------------------------------------中位数-------------------------------------------------------
中位数有一个很好的性质：假设有一批数据，你想找一个数，使得这批数据与它差的绝对值的和最小，你猜它是谁？哈哈
在一个划分成网格的操场上，n 个士兵散乱地站在网格点上，由整数坐标 (x,y) 表示。
士兵们可以沿网格边上、下左右移动一步，但在同时刻任一网格点上只能有 1 名士兵。
按照军官的命令，他们要整齐地列成一个水平队列，即排成队列，即排成 (x,y),(x+1,y),…,(x+n−1,y)。请求出如何选择 x 和 y 的值才能使士兵们以最少的总移动步数排成一列。
输入格式
输入的第一行是一个整数，代表士兵数 n。
第 2 到 (n+1) 行，每行 2 个整数，第 (i+1) 行的整数 xi,yi 代表第 i 个士兵的坐标。
输出格式
输出一行一个整数，代表答案。
输入输出样例
输入 #1复制
5 1 2 2 2 1 3 3 -2 3 3
输出 #1复制
8
说明/提示
对于 100% 的数据，保证 1≤n≤10000，−10000≤x,y≤10000。
纵坐标处理
我们先看纵坐标（其实是纵坐标比较简单）
- 我们假设士兵要移动到的目标纵坐标为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之后再次排序，再取中位数；
#include<iostream>
#include<algorithm>
using namespace std;
int x[10001],y[10001];
int work(int a,int b){
return a>b?a-b:b-a;
}
int main(){
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
sort(x+1,x+n+1);
sort(y+1,y+1+n);
int mid_x,mid_y;
for(int i=1;i<=n;i++) x[i]-=i;
sort(x+1,x+n+1);
if(n%2==0){
int tmp=n/2;
mid_x=(x[tmp]+x[tmp+1])/2;
mid_y=(y[tmp]+y[tmp+1])/2;
}else{
int tmp=n/2;
mid_x=x[tmp+1];
mid_y=y[tmp+1];
}
for(int i=1;i<=n;i++){
ans+=work(mid_x,x[i]);
ans+=work(mid_y,y[i]);
}
cout<<ans<<endl;
return 0;
}
