[bzoj3170][切比雪夫距离]松鼠聚会

本文主要是介绍[bzoj3170][切比雪夫距离]松鼠聚会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。

Input

第一行给出数字N，表示有多少只小松鼠。0<=N<=10^5 下面N行，每行给出x,y表示其家的坐标。
-10^9<=x,y<=109

Output

表示为了聚会走的路程和最小为多少。

Sample Input

6

-4 -1

-1 -2

2 -4

0 2

0 3

5 -2

Sample Output

20

题解

题目要求切比雪夫距离
我们可以推一推

$max(|x1-x2|,|y1-y2|)$
$|x1-x2|+|y1-y2|=max(x1-x2+y1-y2,x2-x1+y1-y2,x1-x2+y2-y1,x2-x1+y2-y1)$
上面分别是切比雪夫距离和曼哈顿距离
我们设
$X1=x1+y1$
$X2=x2+y2$
$Y1=x1-y1$
$Y2=x2-y2$
那么可以化成
$=max(X1-X2,Y2-Y1,Y1-Y2,X2-X1)=max(|X1-X2|,|Y1-Y2|)$
于是(x1,y1)，(x2,y2)的曼哈顿距离可以化成
(x1+y1,x1-y1)，(x2+y2,x2-y2)的切比雪夫距离
反过来推的话，那么
x1+y1=X1,x1-y1=Y1
发现(x1,y1)=((X1+Y1)/2,(X1-Y1)/2)
那么(x1,y1)，(x2,y2)的切比雪夫距离即为((x1+y1)/2,(x1-y1)/2)到((x2+y2)/2,(x2-y2)/2)的曼哈顿距离
同时乘2后答案扩大两倍，可以简化
问题转化为求一个点，使得其他点到他的曼哈顿距离最小
前缀和即可

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
struct node{LL x,y;int op;}w[110000];
bool cmpx(node n1,node n2){return n1.x<n2.x;}
bool cmpy(node n1,node n2){return n1.y<n2.y;}
LL s[110000],g[110000],ans[110000];
int n;
/*
max(|x1-x2|,|y1-y2|)
|x1-x2|+|y1-y2|=max(x1-x2+y1-y2,x2-x1+y1-y2,x1-x2+y2-y1,x2-x1+y2-y1)
X1=x1+y1
X2=x2+y2
Y1=x1-y1
Y2=x2-y2
=max(X1-X2,Y2-Y1,Y1-Y2,X2-X1)
=max(|X1-X2|,|Y1-Y2|)
*/
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){LL x,y;scanf("%lld%lld",&x,&y);w[i].x=(x+y);w[i].y=(x-y);w[i].op=i;}sort(w+1,w+1+n,cmpx);s[0]=0;for(int i=1;i<=n;i++)s[i]=s[i-1]+(w[i].x-w[i-1].x)*(i-1);g[n+1]=0;for(int i=n;i>=1;i--)g[i]=g[i+1]+(w[i+1].x-w[i].x)*(n-i);for(int i=1;i<=n;i++)ans[w[i].op]=s[i]+g[i];sort(w+1,w+1+n,cmpy);s[0]=0;for(int i=1;i<=n;i++)s[i]=s[i-1]+(w[i].y-w[i-1].y)*(i-1);g[n+1]=0;for(int i=n;i>=1;i--)g[i]=g[i+1]+(w[i+1].y-w[i].y)*(n-i);for(int i=1;i<=n;i++)ans[w[i].op]+=s[i]+g[i];LL maxx=1LL<<63-1;for(int i=1;i<=n;i++)maxx=min(maxx,ans[i]);printf("%lld\n",maxx/2);return 0;
}

这篇关于[bzoj3170][切比雪夫距离]松鼠聚会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---