P1889 士兵站队

纵坐标：易知是中位数到各点距离之和最短
横坐标：设最终x1的位置为k+1,所以x2的位置为k+2  ...  xn的位置为k+n
        则各点的横向移动距离为 |x1-(k+1)|+|x2-(k+2)|+...+|xn-(k+n)|
        变形  ==>  |(x1-1)-k|+|(x2-2)-k|+...+|(xn-n)-n|
        通项为  ==>  | (xi-i) - k |
        则要使其和最小，取其(xi-i)的中位数即可

#include<bits/stdc++.h>
using namespace std;
int const N=1e4+7;
int n,ans;
int x[N],y[N];
int main(){
  cin >> n;
  for(int i=1;i<=n;++i){
    cin >> x[i] >> y[i];
  }
  sort(x+1,x+n+1);   //排完之后在减  //保证其横向移动的距离最小，就近原则
  for(int i=1;i<=n;++i){
    x[i]-=i;
  } 
  sort(x+1,x+n+1);
  sort(y+1,y+n+1);
  int zx,zy;
  if(n%2==1){
    zx=x[n/2+1];
    zy=y[n/2+1];
  } 
  else{
    zx=(x[n/2]+x[n/2+1])/2;
    zy=(y[n/2]+y[n/2+1])/2;
  }
  for(int i=1;i<=n;++i){
    ans+=abs(x[i]-zx);
    ans+=abs(y[i]-zy); 
  }
  cout << ans;
  return 0;
}