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

作者: wjyyy 分类: 几何,分类目录,数学,解题报告 发布时间: 2018-08-14 14:02

点击量:14

 

    什么什么距离的涨姿势了

 

题目描述

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

 

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

 

说点什么

avatar
  Subscribe  
提醒
/* */