[TJOI2013] 松鼠聚会 题解

切比雪夫距离

切比雪夫距离指的是在平面上的两个点\((x_1,y_1)\),\((x_2,y_2)\)之间横纵坐标之差绝对值中的大者。用公式表示则是\(f(a,b)=max(|x_a-x_b|,|y_a-y_b|)\)。

切比雪夫距离与曼哈顿距离之间可以相互转换

切比雪夫—>曼哈顿：\((x_1,y_1)\),\((x_2,y_2)\)->\((\frac{x_1+y_1}{2},\frac{x_1-y_1}{2})\),\((\frac{x_2+y_2}{2},\frac{x_2-y_2}{2})\)

曼哈顿—>切比雪夫：\((x_1,y_1)\),\((x_2,y_2)\)->\((x_1+y_1,x_1-y_1)\),\((x_2+y_2,x_2-y_2)\)

这样就可以将切比雪夫距离转化为曼哈顿距离进行计算了。

好的，那么这道题就将切比雪夫下的坐标转化成曼哈顿下的坐标即可。为了防止浮点数对时间复杂度的影响，我们转化时先不除二，等到判断时再除二。

那么如何快速求出曼哈顿距离之和呢

可以考虑到，我们以\(x\)为关键字按升序排序，那么我们求解\(x\)坐标的差值的绝对值时就只需进行前缀和即可，对于\(y\)坐标，我们只需排序，然后对于一个点，我们进行二分查找其对应\(y\)坐标在有序数列中的位置，然后再进行前缀和即可。

代码

/*
 * Author:Ehundategh
 * Update:2023/10/10
 * Title:squ.cpp
 * You steal,I kill
 */
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
using namespace std;
struct node{
    long long X,Y;
}Node[MAXN];
bool cmp(node a,node b){return a.X<b.X;}
long long n,PreX[MAXN],PreY[MAXN],CopyY[MAXN],Ans=0x7fffffffffffffff;
node Change(node a){
    int Temp=a.X;
    a.X=a.X+a.Y;
    a.Y=Temp-a.Y;
    return a;
}
long long Check(int Pos){
    long long Ret=0,Y=Node[Pos].Y;
    Ret+=(Pos-1)*Node[Pos].X-PreX[Pos-1];
    Ret+=PreX[n]-PreX[Pos]-(n-Pos)*Node[Pos].X;
    Pos=lower_bound(CopyY+1,CopyY+n+1,Node[Pos].Y)-CopyY;
    Ret+=(Pos-1)*Y-PreY[Pos-1];
    Ret+=PreY[n]-PreY[Pos]-(n-Pos)*Y;
    return Ret>>1;
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&Node[i].X,&Node[i].Y);
        Node[i]=Change(Node[i]);        
        CopyY[i]=Node[i].Y;
    }
    sort(CopyY+1,CopyY+n+1);
    sort(Node+1,Node+n+1,cmp);
    for(int i=1;i<=n;i++){
        PreX[i]=PreX[i-1]+Node[i].X;
        PreY[i]=PreY[i-1]+CopyY[i];
    }
    for(int i=1;i<=n;i++){
        Ans=min(Check(i),Ans);
    }
    printf("%lld",Ans);
    return 0;
}