BZOJ 3170 [Tjoi 2013]松鼠聚会
题目描述
有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。
输入
第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5
下面N行，每行给出x,y表示其家的坐标。
-10^9<=x,y<=10^9
输出
表示为了聚会走的路程和最小为多少。
样例输入
6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2
样例输出
20
解题思路
新学了一个姿势——切比雪夫距离(题目中定义的那个距离)。
A(x1,y1)与B(x2,y2)的切比雪夫距离等于A’(x1+y1,x1-y1)和B’(x2+y2,x2-y2)的曼哈顿距离。证明挺简单的。
把每个点$(x,y)$转换成$(x+y,x-y)$，然后枚举松鼠们的目的地，找出最短距离。枚举目的地统计答案用前缀和优化。
源代码
来自于http://blog.csdn.net/aarongzk/article/details/51138617
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define maxn 100005 #define inf 1000000000000000000ll using namespace std; int n,pos,x[maxn],y[maxn]; ll ans,tmp,sumx[maxn],sumy[maxn]; struct data{ll x,y;}a[maxn]; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read(); F(i,1,n) { int xx=read(),yy=read(); x[i]=a[i].x=xx+yy; y[i]=a[i].y=xx-yy; } sort(x+1,x+n+1);sort(y+1,y+n+1); F(i,1,n) sumx[i]=sumx[i-1]+x[i],sumy[i]=sumy[i-1]+y[i]; ans=inf; F(i,1,n) { pos=lower_bound(x+1,x+n+1,a[i].x)-x; tmp=sumx[n]-sumx[pos]-a[i].x*(n-pos)+a[i].x*pos-sumx[pos]; pos=lower_bound(y+1,y+n+1,a[i].y)-y; tmp+=sumy[n]-sumy[pos]-a[i].y*(n-pos)+a[i].y*pos-sumy[pos]; ans=min(ans,tmp); } printf("%lld\n",ans/2); return 0; }