首页 > 代码库 > bzoj 3170 Tjoi 2013 松鼠聚会 曼哈顿距离&&切比雪夫距离
bzoj 3170 Tjoi 2013 松鼠聚会 曼哈顿距离&&切比雪夫距离
因为曼哈顿距离很好求，所以要把每个点的坐标转换一下。
转自：http://blog.csdn.net/slongle_amazing/article/details/50911504
题解
两个点的切比雪夫距离为d=max(|x1?x2|,|y1?y2|)
写一下曼哈顿距离的常用处理方法
两个点(x1,y2),(x2,y2)
其曼哈顿距离=|x1?x2|+|y1?y2|
因为|x1?x2|=max(x1?x2,x2?x1)
所以可以写成=max(x1?x2+y1?y2,x1?x2+y2?y1,x2?x1+y1?y2,x2?x1+y2?y1)
=max((x1+y1)?(x2+y2),(x1?y1)?(x2?y2),?(x1?y1)+(x2?y2),?(x1+y1)+(x2+y2))
=max(|(x1+y1)?(x2+y2)|,|(x1?y1)?(x2?y2)|)
令x′=x+y,y′=x?y=max(|x′1?x′2|,|y′1?y′2|)
这样曼哈顿距离就被转化为了切比雪夫距离
同理,我们把切比雪夫距离转化为曼哈顿距离(x,y)=(x+y2,x?y2)
就转化为了n?1个点到一个点的曼哈顿距离最小
计算曼哈顿距离x和y分开计算即可
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #define ll long long 6 #define N 100005 7 using namespace std; 8 int n; 9 struct node 10 { 11 int x,y,id; 12 friend bool operator < (node aa,node bb) 13 { 14 return aa.x<bb.x; 15 } 16 }a[100005]; 17 ll ans[N],sum[N]; 18 bool cmp(node aa,node bb) 19 { 20 return aa.y<bb.y; 21 } 22 int main() 23 { 24 scanf("%d",&n);int t1,t2; 25 for(int i=1;i<=n;i++) 26 { 27 scanf("%d%d",&t1,&t2); 28 a[i].x=t1+t2;a[i].y=t1-t2;a[i].id=i; 29 } 30 sort(a+1,a+n+1); 31 for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].x; 32 for(int i=1;i<=n;i++) 33 { 34 ans[a[i].id]+=(ll)a[i].x*(i-1)-sum[i-1]; 35 ans[a[i].id]+=(sum[n]-sum[i])-((ll)a[i].x*(n-i)); 36 } 37 sort(a+1,a+n+1,cmp); 38 for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].y; 39 for(int i=1;i<=n;i++) 40 { 41 ans[a[i].id]+=(ll)a[i].y*(i-1)-sum[i-1]; 42 ans[a[i].id]+=(sum[n]-sum[i])-((ll)a[i].y*(n-i)); 43 } 44 ll mx=1ll<<62; 45 for(int i=1;i<=n;i++)mx=min(mx,ans[i]); 46 printf("%lld\n",mx/2); 47 return 0; 48 }
bzoj 3170 Tjoi 2013 松鼠聚会 曼哈顿距离&&切比雪夫距离
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。