poj1723

题意

​ 给定$n$个点的坐标，每次能在$x$轴或$y$轴移动一个单位，让你用最少的移动步数，使得这$n$个点在$x$轴上相邻（间隔1个单位），在$y$轴上的位置相同。

求解

这个问题分为几步思考：

1. ​ 显然我们可以把两个轴作为两个问题分开讨论，$y$轴上显然是移动到中位数的坐标了，问题就在于$x$轴。

2. ​ 我开始的思路是，$x$轴上的数排序后，作差分数组，再让每个数和1相减，每次能进行相邻两个数一个加一一个减一的操作，最少操作次数使其全为0 。想了会发现没什么思路。

3. ​ 后面还是看了下别人的写法：

令排序后的数组的$n$个数为$x_1,x_2…x_n$，于是我们设移动之后第一个点的前一个位置为$a$。

由于完成操作之后，这$n$个有序的点是相邻的，于是我们需要得到的最小值是：

$$ \left| x_1-(a+1) \right|+ \left| x_2-(a+2) \right|+ …+ \left| x_n-(a+n) \right| \\ \Rightarrow \left| (x_1-1)-a \right|+ \left| (x_2-2)-a \right|+ …+ \left| (x_n-n)-a \right| $$

很显而易见了，问题就转化成了求$x_1-1,x_2-2…x_n-n$到某个数是最小距离和，中位数就好了。

启发

1. 求解2中的问题，其实相当于这个问题倒过来了，我们只要加上一个数，求前缀和数组，再求最短距离和就好了，在codeforces中喜欢出这类的题的。
2. 还是要多尝试把数学和模型相互转化和抽象。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,ll> P;
const int maxn=20000+100;

ll res=0;
int n,x[maxn],y[maxn];

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>x[i]>>y[i]; 
    }
    sort(y+1,y+1+n) ;
    sort(x+1,x+1+n) ;
    for(int i=1;i<=n;i++) {
        x[i]-=i;
    }
    sort(x+1,x+1+n) ;
    int mid=(n+1)/2;
    for(int i=1;i<=n;i++) {
        res+=abs(y[i]-y[mid]);
        res+=abs(x[i]-x[mid]);

    }
    cout<<res<<endl;

    return 0;
}