[TJOI2013]松鼠聚会 曼哈顿距离

[TJOI2013]松鼠聚会

luogu P3964
首先容易得到两点间距离是(max(|x_1-x_2|, |y_1-y_2|))（即切比雪夫距离）
然后有个套路：原((x,y))求曼哈顿距离可以转换为((x+y,x-y))求切比雪夫距离，同样的((x,y))求切比雪夫距离就是求((frac{x+y}{2},frac{x-y}{2}))曼哈顿距离。
然后考虑优化求(n-1)个总曼哈顿距离的过程
先所有点以(x,y)分别作为关键字排序一遍，对于点(i)的(sumx)可得

[(x_i-x_1)+(x_i-x_2)+cdots+(x_i-x_i)+(x_{i+1}-x_i)+(x_{i+2}-x_i)+cdots +(x_n-x_i)\ i imes x_i-sum^i_{j=1} x_j+sum^n_{j=i+1} x_j-(n-i) imes x_i ]

(sumy)同理
不难发现我们维护一个前缀和即可。
另外为了防止坐标出现小数所以我们就不除2了，在最后答案的时候再除2

#include <cstdio>
#include <climits>
#include <algorithm>
#define MAXN 100010
#define ll long long
using namespace std;
int n;
struct nod{
    int x,y;
} a[MAXN];
int sx[MAXN],sy[MAXN];
ll sumx[MAXN],sumy[MAXN];
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        int xx,yy;
        scanf("%d %d", &xx, &yy);
        a[i].x=xx+yy;
        a[i].y=xx-yy;
        sx[i]=a[i].x;
        sy[i]=a[i].y;
    }
    sort(sx+1, sx+1+n);
    sort(sy+1, sy+1+n);
    for(int i=1;i<=n;++i) sumx[i]=sumx[i-1]+sx[i];
    for(int i=1;i<=n;++i) sumy[i]=sumy[i-1]+sy[i];
    ll ans=LLONG_MAX;
    for(int i=1;i<=n;++i){
        ll res=0;
        int k=lower_bound(sx+1, sx+1+n, a[i].x)-sx;
        res+=(ll)a[i].x*k-sumx[k]+sumx[n]-sumx[k]-(ll)(n-k)*a[i].x;
        k=lower_bound(sy+1, sy+1+n, a[i].y)-sy;
        res+=(ll)a[i].y*k-sumy[k]+sumy[n]-sumy[k]-(ll)(n-k)*a[i].y;
        ans=min(ans, res);
    }
    printf("%lld", ans/2);
    return 0;
}