　　题目传送门

松鼠聚会

题目描述

草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点x,y表示,两个点的距离定义为点(x,y)和它周围的8个点(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)距离为1。

输入输出格式

输入格式：

第一行是一个整数N,表示有多少只松鼠。接下来N行,第i行是两个整数x和y,表示松鼠i的家的坐标

输出格式：

一个整数,表示松鼠为了聚会走的路程和最小是多少。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

样例解释

在第一个样例中,松鼠在第二只松鼠家(-1,-2)聚会;在第二个样例中,松鼠在第一只松鼠家(0.0)聚会。

数据范围

30%的数据，0 ≤ N ≤ 1000

100%的数据，0 ≤ N ≤ 100000; −10^9 ≤ x, y ≤ 10^9

　　分析：

　　这道奇妙的题让蒟蒻认识了切比雪夫距离这个奇妙的东西，关于切比雪夫距离可以参照julao的博客。

　　关于这道题，我们把切比雪夫距离转换成曼哈顿距离，然后用前缀和+二分答案优化一下就可以了。

　　Code：

//It is made by HolseLee on 6th Nov 2018

//Luogu.org P3964

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+;

int n,x[N],y[N],px[N],py[N];

ll sumx[N],sumy[N],ans;

inline int read()

{

    char ch=getchar(); int x=; bool flag=false;

    while( ch<'' || ch>'' ) {

        if( ch=='-' ) flag=true; ch=getchar();

    }

    while( ch>='' && ch<='' ) {

        x=x*+ch-''; ch=getchar();

    }

    return flag ? -x : x;

}

void getsum()

{

    for(int i=; i<=n; ++i) sumx[i]=sumx[i-]+x[i];

    for(int i=; i<=n; ++i) sumy[i]=sumy[i-]+y[i];

}

inline ll binary_x(int u)

{

    ll l=, r=n, mid,ret=n;

    while( l<=r ) {

        mid=(l+r)>>;

        if( x[mid]<=px[u] ) ret=mid, l=mid+;

        else r=mid-;

    }

    return ret;

}

inline ll binary_y(int u)

{

    ll l=, r=n, mid,ret=n;

    while( l<=r ) {

        mid=(l+r)>>;

        if( y[mid]<=py[u] ) ret=mid, l=mid+;

        else r=mid-;

    }

    return ret;

}

inline ll getans(int u)

{

    ll xpos=binary_x(u);

    ll ansx=xpos*px[u]-sumx[xpos]+sumx[n]-sumx[xpos]-(n-xpos)*px[u];

    ll ypos=binary_y(u);

    ll ansy=ypos*py[u]-sumy[ypos]+sumy[n]-sumy[ypos]-(n-ypos)*py[u];

    return ansx+ansy;

}

int main()

{

    n=read(); int a,b;

    for(int i=; i<=n; ++i) {

        a=read(), b=read();

        x[i]=px[i]=a+b; y[i]=py[i]=a-b;

    }

    sort(x+,x+n+); sort(y+,y+n+);

    getsum();

    ans=1e18;

    for(int i=; i<=n; ++i) {

        ll now=getans(i);

        ans=min(now,ans);

    }

    printf("%lld\n",ans>>1ll);

    return ;

}

巴特西

洛谷P3964 [TJOI2013]松鼠聚会 [二分答案，前缀和，切比雪夫距离]