BZOJ3170: [Tjoi2013]松鼠聚会

时间：2023-03-08 22:13:20

【传送门：BZOJ3170】

简要题意：

　　给出n个点的坐标，规定两个点的距离=max(|x1-x2|,|y1-y2|)

　　要求选出一个点，使得这个点到所有点的距离和最小

题解：

　　切比雪夫转换例题

　　将一个点(x,y)的坐标变为(x+y,x−y)后

　　原坐标系中的切比雪夫距离=新坐标系中的曼哈顿距离

　　求最小曼哈顿距离就行了

　　关于切比雪夫与曼哈顿距离转化请左转

参考代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#define Maxn 110000

#define mes(x,y) memset(x,y,sizeof(x))

using namespace std;

typedef long long LL;

struct node{int x,id;}X[Maxn],Y[Maxn];

bool cmp(node n1,node n2){return n1.x<n2.x;}

LL Lx[Maxn],Ly[Maxn],Rx[Maxn],Ry[Maxn];

int tx[Maxn],ty[Maxn];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        X[i].x=x+y;Y[i].x=x-y;

        X[i].id=Y[i].id=i;

    }

    sort(X+,X+n+,cmp);sort(Y+,Y+n+,cmp);

    for(int i=;i<=n;i++) tx[X[i].id]=i,ty[Y[i].id]=i;

    for(int i=;i<=n;i++)

    {

        Lx[i]=Lx[i-]+LL(i-)*(X[i].x-X[i-].x);

        Ly[i]=Ly[i-]+LL(i-)*(Y[i].x-Y[i-].x);

    }

    for(int i=n-;i>=;i--)

    {

        Rx[i]=Rx[i+]+LL(n-i)*(X[i+].x-X[i].x);

        Ry[i]=Ry[i+]+LL(n-i)*(Y[i+].x-Y[i].x);

    }

    LL ans=1LL<<;

    for(int i=;i<=n;i++) ans=min(ans,Lx[tx[i]]+Ly[ty[i]]+Rx[tx[i]]+Ry[ty[i]]);

    printf("%lld\n",ans/);

    return ;

}

相关文章