洛谷 P3964 [TJOI2013]松鼠聚会 题解【数学】【几何】

点击量：171

    什么什么距离的涨姿势了

目录

题目描述

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

 

每个小松鼠的家可以用一个点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：

6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2

输出样例#1：

20

输入样例#2：

6
0 0
2 0
-5 -2
2 -2
-1 2
4 0

输出样例#2：

15

说明

样例解释

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

 

数据范围

30%的数据，0 ≤ N ≤ 1000

 

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

题解：

    这个题如果仔细思考是可以想出$ O(N^2)$算法的。对于一个终点，每个松鼠可以贪心地先走对角线，然后与终点在同一行/同一列时再加上距离。因此到点$ i$的距离和就是$$\sum_{j=1}^n\max{|x_j-x_i|,|y_j-y_i|}$$

    其实这个平方可以被前缀和优化掉。但是我们知道，这个东西既有绝对值又有max，前缀和是可以支持加减操作的，max不适合，因此不能直接做。

    在这个题中，$ \max \{ |x_j-x_i|,|y_j-y_i| \}$就是切比雪夫距离。它是在国际象棋上一个点移动到另一个点的最少步数，也就是$ \Delta x$和$ \Delta y$的较大值。我们可以通过一个结论来把它转化为曼哈顿距离。两点间的曼哈顿距离就是$ \Delta x+\Delta y$。

    假设一个点的坐标是$ (x,y)$，那么它与其它点算切比雪夫距离时，可以把它们的坐标变为$ \left( \frac {x+y}2,\frac {x-y}2 \right)$，此时算两点的曼哈顿距离就可以了。算曼哈顿距离可以利用前缀和优化，所有点到$ i$点的曼哈顿距离和就是$$ \sum_{j=1}^n|x_j-x_i|+|y_j-y_i|$$

    我们可以把这个$ \sum$展开，发现它是$ 2n$个式子相加。这样我们就可以把横坐标比$ x_i$小的前缀和减掉，再用横坐标大于$ x_i$的后缀和减去自己，这里要注意系数。我们因为用了前缀和，所以$ x$是有序的，在这里不需要$ x_i$和$ y_i$一一对应，所以可以额外把$ y$坐标排序，然后二分查找属于自己的位置就可以了。时间复杂度$ O(n\log n)$。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
struct pnt
{
    double x,y;
    friend bool operator <(pnt a,pnt b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
    pnt(double x,double y)
    {
        this->x=x;
        this->y=y;
    }
    pnt(){}
}a1[100100],a2[100100];
bool cmp(pnt a,pnt b)
{
    if(a.y!=b.y)
        return a.y<b.y;
    return a.x<b.x;
}
double sumx[100100];
double sumy[100100];
int main()
{
    int n;
    scanf("%d",&n);
    double x,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&x,&y);
        a1[i]=pnt((x+y)/2.0,(x-y)/2.0);//坐标转换，记得用double
        a2[i]=a1[i];
    }
    std::sort(a1+1,a1+1+n);
    std::sort(a2+1,a2+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        sumx[i]=a1[i].x+sumx[i-1];
        sumy[i]=a2[i].y+sumy[i-1];
    }

    double ans=0x7fffffffffffffffll;
    for(int i=1;i<=n;i++)
    {
        double sum=(i-1)*a1[i].x-sumx[i-1]+sumx[n]-sumx[i]-(n-i)*a1[i].x;//x前缀和
        int l=1,r=n,mid;
        while(l<r)
        {
            mid=l+r>>1;
            if(a2[mid].y<=a1[i].y)
                l=mid+1;
            else
                r=mid;
        }
        l--;
        sum+=(l-1)*a1[i].y-sumy[l-1]+sumy[n]-sumy[l]-(n-l)*a1[i].y;//y前缀和
        ans=ans<sum?ans:sum;//比较答案
    }
    printf("%.0lf\n",ans);//因为原题是整数，所以输出整数
    return 0;
}