脚本宝典收集整理的这篇文章主要介绍了洛谷P3964 [TJOI2013]松鼠聚会，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

这个小辣鸡怎么连切比雪夫距离都不会啊。。。

题目

https://www.luogu wangt.cc wangt.cc /PRoblem/P3964

思路

切比雪夫距离

定义

点((x1,y1))到((x2,y2))的切比雪夫距离为： (dis=max(lvert x1-x2rvert,lvert y1-y2rvert))

切比雪夫距离与曼哈顿距离的变换

显然这个东西既包含绝对值又包含最值，非常不好处理。

但是我们有一种转化方法珂以将切比雪夫距离转化成曼哈顿距离。当然逆变换也必然是存在的。我这里推一遍曼哈顿距离到切比雪夫距离的变换。

假设两个点为((x1,y1))，((x2,y2))，那么它们的曼哈顿距离为：(lvert x1-x2rvert + lvert y1-y2rvert)，考虑把绝对值拆掉：

(lvert x1-x2rvert + lvert y1-y2rvert)=(max(x1-x2+y1-y2 , x1-x2+y2-y1 , x2-x1+y1-y2 , x2-x1+y2-y1))

现在发现式子已经变成了一个max的形式。注意到(x1-x2+y1-y2=-(x2-x1+y2-y1))，把式子中互为相反数的部分并在一起，得：

(max(max(x1-x2+y1-y2,x2-x1+y2-y1),max(x1-x2+y2-y1,x2-x1+y1-y2)))

就是(max(lvert x1-x2+y1-y2rvert,lvert x1-x2-(y1-y2)rvert))

=(max(lvert x1+y1-(x2+y2)rvert,lvert x1-y1-(x2-y2)rvert))

对照切比雪夫距离的定义，我们令 (x1'=x1+y1) , (y1'=x1-y1) , (x2'=x2+y2) , (y2'=x2-y2)

则距离可写为 (max(vert x1'-x2'rvert,lvert y1'-y2'rvert))

所以曼哈顿意义下的((x,y))，对应于切比雪夫意义下的((x+y,x-y))

同样，我们珂以很容易地做一个逆变换，把切比雪夫意义下的((x,y))映射到曼哈顿意义下的((frac{x+y}{2},frac{x-y}{2}))。

（这堆式子用了markdown还是好丑啊，其实自己在草稿上推一遍挺快的qwq）

解题

现在问题变成了，给出一堆点，求其中的一个点，使所有点到该点的曼哈顿距离之和最小。

枚举每一个点，计算集合点在该点的代价。那就是很经典的珂以用前缀和维护的问题了。

代码

#include<cstdio>
#include<cstdlib>
#include<algorIThm>
#define ll long long
#define maxn (int)(1e5+10)
using namespace std;
struct point{
    ll x,y;
} p[maxn];
bool cmp1(point p1,point p2){
    return p1.x<p2.x;
}
bool cmp2(point p1,point p2){
    return p1.y<p2.y;
}
ll X[maxn],Y[maxn];
ll pre_x[maxn],pre_y[maxn];
int n;
ll cal(int id){
    ll sum=0;
    int i;
    i=lower_bound(X+1,X+n+1,p[id].x)-X;
    sum+=(p[id].x*(i-1)-pre_x[i-1])+(pre_x[n]-pre_x[i-1]-p[id].x*(n-i+1));
    i=lower_bound(Y+1,Y+n+1,p[id].y)-Y;
    sum+=(p[id].y*(i-1)-pre_y[i-1])+(pre_y[n]-pre_y[i-1]-p[id].y*(n-i+1));
    return sum;
}
int main(){
    int i;
    ll tx,ty;
    ll ans=-1;
    scanf("%d",&amp;n);
    for(i=1;i<=n;++i){
        scanf("%lld%lld",&tx,&ty);
        p[i].x=tx+ty;p[i].y=tx-ty;
    }
    sort(p+1,p+n+1,cmp2);
    for(i=1;i<=n;++i){
        Y[i]=p[i].y;
        pre_y[i]=pre_y[i-1]+Y[i];
    }
    sort(p+1,p+n+1,cmp1);
    for(i=1;i<=n;++i){
        X[i]=p[i].x;
        pre_x[i]=pre_x[i-1]+X[i];
    }
    for(i=1;i<=n;++i){
        ans=ans<0?cal(i):min(ans,cal(i));
    }
    printf("%lld",ans/2);
    // System("pause");
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的洛谷P3964 [TJOI2013]松鼠聚会全部内容，希望文章能够帮你解决洛谷P3964 [TJOI2013]松鼠聚会所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。