题解 P3964 【[TJOI2013]松鼠聚会】

我的博客原文链接：http://www.cnblogs.com/Elfish/p/7931766.html 本题两点间的距离是max(|x1-x2|,|y1-y2|)，曾经在黄学长的博客里看到过一个转化  求这个距离可以把点的坐标都转化成 (x+y)/2,(x-y)/2  然后的曼哈顿距离就是这个了 这个好像叫 切比雪夫距离 之后我们预处理前缀和，枚举源点就可以了。 记得都开longlong 我WA的很悲惨 ```cpp #include<bits/stdc++.h> #define MAXN 100005 using namespace std; int read(){ int x=0,t=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*t; } struct Node{ long long X,Y; }a[MAXN]; int N,x[MAXN],y[MAXN],pos; long long ans=1ll<<62,s1[MAXN],s2[MAXN]; int main() { N=read(); for(int i=1;i<=N;i++){ int p=read(),q=read(); x[i]=a[i].X=p+q; y[i]=a[i].Y=p-q; } sort(x+1,x+N+1); sort(y+1,y+N+1); for(int i=1;i<=N;i++) s1[i]=s1[i-1]+x[i], s2[i]=s2[i-1]+y[i]; for(int i=1;i<=N;i++){ long long tmp=0; pos=lower_bound(x+1,x+N+1,a[i].X)-x; tmp+=s1[N]-s1[pos]-a[i].X*(N-pos)+a[i].X*pos-s1[pos]; pos=lower_bound(y+1,y+N+1,a[i].Y)-y; tmp+=s2[N]-s2[pos]-a[i].Y*(N-pos)+a[i].Y*pos-s2[pos]; ans=min(ans,tmp); } printf("%lld\n",ans/2); return 0; } ```