洛谷3964 [TJOI2013]松鼠聚会

题目描述

草原上住着一群小松鼠,每个小松鼠都有一个家。时间长了,大家觉得应该聚一聚。但是草原非常大,松鼠们都很头疼应该在谁家聚会才最合理。

每个小松鼠的家可以用一个点x,y表示,两个点的距离定义为点(x,y)和它周围的8个点(x-1,y)(x+1,y),(x,y-1),(x,y+1).(x-1,y+1),(x-1,y-1),(x+1,y+1),(x+1,y-1)距离为1。

输入输出格式

输入格式：

第一行是一个整数N,表示有多少只松鼠。接下来N行,第i行是两个整数x和y,表示松鼠i的家的坐标

输出格式：

一个整数,表示松鼠为了聚会走的路程和最小是多少。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

样例解释

在第一个样例中,松鼠在第二只松鼠家(-1,-2)聚会;在第二个样例中,松鼠在第一只松鼠家(0.0)聚会。

数据范围

30%的数据，0 ≤ N ≤ 1000

100%的数据，0 ≤ N ≤ 100000; −10^9 ≤ x, y ≤ 10^9

做法

本题两点间的距离是max(|x1-x2|,|y1-y2|)，曾经在黄学长的博客里看到过一个转化

求这个距离可以把点的坐标都转化成 (x+y)/2,(x-y)/2 然后的曼哈顿距离就是这个了

这个好像叫切比雪夫距离

之后我们预处理前缀和，枚举源点就可以了。

记得都开longlong 我WA的很悲惨

#include<bits/stdc++.h>

#define MAXN 100005

using namespace std;

int read(){

    int x=,t=;char c=getchar();

    while(c<''||c>''){if(c=='-')t=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*t;

}

struct Node{

    long long X,Y;

}a[MAXN];

int N,x[MAXN],y[MAXN],pos;

long long ans=1ll<<,s1[MAXN],s2[MAXN];

int main()

{

    N=read();

    for(int i=;i<=N;i++){

        int p=read(),q=read();

        x[i]=a[i].X=p+q;

        y[i]=a[i].Y=p-q;

    }

    sort(x+,x+N+);

    sort(y+,y+N+);

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

        s1[i]=s1[i-]+x[i],

        s2[i]=s2[i-]+y[i];

    for(int i=;i<=N;i++){

        long long tmp=;

        pos=lower_bound(x+,x+N+,a[i].X)-x;

        tmp+=s1[N]-s1[pos]-a[i].X*(N-pos)+a[i].X*pos-s1[pos];

        pos=lower_bound(y+,y+N+,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/);

    return ;

}

巴特西