BZOJ 3170 [Tjoi 2013]松鼠聚會 切比雪夫距離-->曼哈頓距離

Description

有N個小松鼠，它們的家用一個點x,y表示，兩個點的距離定義為：點(x,y)和它周圍的8個點即上下左右四個點和對角的四個點，距離為1。現在N個松鼠要走到一個松鼠家去，求走過的最短距離。

Input

第一行給出數字N，表示有多少隻小松鼠。0<=N<=10^5

下面N行，每行給出x,y表示其家的坐标。

-10^9<=x,y<=10^9

Output

表示為了聚會走的路程和最小為多少。

Sample Input

6

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

Sample Output

20

HINT

​​傳送門​​

……好菜啊才會切比雪夫距離……

根據題意可以斜走，那麼(x1,y1)(x2,y2)之間的距離就是max(|x1-x2|,|y1-y2|)

然後……我就不會了= =

百度了一下發現這個東西叫做切比雪夫距離……

然後它可以轉化成曼哈頓距離去的。

具體過程差不多就是拆成4個，取max這樣子

反正推出來是(x,y)變成（(x-y)/2，(x+y)/2）

然後距離就變成了兩點之間的曼哈頓距離。

如何統計其它點到這個點的曼哈頓距離……

隻要統計比x小的和與個數、比x大的和與個數就可以算出x到其它所有點的距離之和，

y同理，，不難了解吧……

就是說x和y是獨立的……然後分開來求就通過去掉絕對值來搞。。

那麼這個亂搞就好了……

樹狀數組什麼的還要離散化，直接排序+二分水水掉……

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int
    N=100005;
int n;
ll Y[N],sumx[N],sumy[N];
struct node{ll l,r;}X[N];
bool cmp(node p,node q){return p.l<q.l;}
void Pre(){
    int t1,t2;
    for (int i=1;i<=n;i++){
        scanf("%d%d",&t1,&t2);
        X[i].l=t1-t2,X[i].r=t1+t2;
        Y[i]=X[i].r;
    }
    sort(X+1,X+1+n,cmp),sort(Y+1,Y+1+n);
    sumx[0]=0LL,sumy[0]=0LL;
    for (int i=1;i<=n;i++) sumx[i]=sumx[i-1]+X[i].l;
    for (int i=1;i<=n;i++) sumy[i]=sumy[i-1]+Y[i];
}
ll solve(){
    ll ans=1e18;
    for (int i=1;i<=n;i++){
        ll t=X[i].l*(i-1)-sumx[i-1]+sumx[n]-sumx[i]-X[i].l*(n-i);
        int j=lower_bound(Y+1,Y+1+n,X[i].r)-Y;
        t+=X[i].r*(j-1)-sumy[j-1]+sumy[n]-sumy[j]-X[i].r*(n-j);
        ans=min(ans,t);
    }
    return ans>>1LL;
}
int main(){
    scanf("%d",&n);
    Pre();
    printf("%lld\n",solve());
    return 0;
}