题解 P3964 松鼠聚会

Rbu_nas · 2019-11-11 21:53:52 · 题解

一道有趣的题OwO

题意简述：在 n 个点中找到一个点 x，使其他 n-1 个点到 x 的 切比雪夫距离 之和最小。求距离和的最小值。

然而题面只告诉了我们「一个点到周围的八个点距离为 1」，这种距离计量方式是啥意思呢。其实，这就是 切比雪夫距离 的定义，也称为 棋盘距离。

若二个向量或二个点 p、and q，其坐标分别为 p_i 及 q_i，则两者之间的切比雪夫距离定义如下：

这也等于以下 L_p 度量的极值：

因此切比雪夫距离也称为 L_{∞} 度量。

以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。

在平面几何中，若二点 p 及 q 的直角坐标系坐标为 (x_1,y_1) 及 (x_2,y_2)，则切比雪夫距离为：

总结一下，切比雪夫距离指的是两个点各座标数值差的最大值，也就是 \max(|x_2-x_1|,|y_2-y_1|)。在棋盘中就表现为一个不在边缘的格子，到周围 8 个格子都是 1 步的距离，所以也被称作棋盘距离。

举个例子：

切比雪夫距离是常用的距离表示方式之一，这里同时介绍一下其他的距离表示方法。

欧几里得距离

初中数学教材介绍的两点间距离表示。

设 A(x_1,y_1),B(x_2,y_2) 那么 |AB|=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

一般模型：在一个坐标系上，求从一个点到另一个点的最短几何距离。
曼哈顿距离

二维空间内，两个点之间的曼哈顿距离为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。它可以很快求出各点距离和。

即 A(x_1,y_1),B(x_2,y_2) 那么 |AB|=|x_2-x_1|+|y_2-y_1|

一般模型：网格图中从一个点走向另一个点的最短距离。
切比雪夫距离

详细解释可参见上文维基百科的选段。

通俗的讲，有 A(x_1,y_1),B(x_2,y_2)，那么切比雪夫距离定义为 \max(|x_2-x_1|,|y_2-y_1|)

一般模型：棋盘上或者在图中一个点到另外相邻八个点的距离为 1。

现在我们已知了题目的询问原来是求切比雪夫距离的和，可是貌似没啥用啊。

考虑枚举每一个点，都要穷举其他 n-1 个点到这个点的距离，复杂度不能接受。柿子 \max(\Delta x_1,\Delta y_1)+\max(\Delta x_2,\Delta y_2)+\dots+max(\Delta x_n,\Delta y_n) 很烦，如何将其转换呢？

经过观察可以发现，切比雪夫距离 \max(\Delta x,\Delta y) 和曼哈顿距离 (\Delta x+\Delta y) 很相似（事实上也没啥距离表示和切比雪夫距离相似的

由于计算每个点取 max 复杂度跑不掉了，可不可以考虑向曼哈顿距离转化呢？（曼哈顿距离的优势马上就要展现出来了

{}

尝试一下。康康分类讨论曼哈顿距离的公式可不可以化开。

D=|x_2-x_1|+|y_2-y_1|

D=\max\left(x_2-x_1+y_2-y_1,\ x_1-x_2+y_2-y_1,\ x_1-x_2+y_1-y_2,\ x_2-x_1+y_1-y_2\right)

D=\max\{\ \left|(x_2+y_2)-(x_1+y_1)\right|,\ \left|(x_2-y_2)-(x_1-y_1)\right|\ \}

{}

哇哦，这个和 D_{\texttt{Chess}}=\max(|x_2-x_1|,|y_2-y_1|) 形式上长的真像，很容易就能发现曼哈顿意义下的 (x_1,y_1) (x_2,y_2) 两点的距离转化为了切比雪夫意义下的 (x_2+y_2,x_2-y_2) (x_1+y_1,x_1-y_1) 两点的距离。

推广到更一般的情况，给出曼哈顿意义下的坐标 (x,y)，可转化成切比雪夫意义下的坐标 (x+y,x-y)。

反过来，我们也能通过切比雪夫意义下的坐标 (x,y) 转化为曼哈顿意义下的 (\frac{x+y}{2},\frac{x-y}{2})，正是我们想要的。

这个具体有什么用呢？上文已提到了曼哈顿距离求和非常快的优势，现在我们再研究研究怎么个快速求和。

还是从根式推起。

设 dis(i,j) 为曼哈顿意义下 i 到 j 的曼哈顿距离。若当前枚举的终点为 j 那么 ans=\sum\limits_{i=1}^n dis(i,j)，这也是 O(N^2) 的。稍稍再化简一下：

\sum\limits_{i=1}^n dis(i,j)

=dis(1,j)+dis(2,j)+\dots+dis(n,j)

{}

以 dis(i,j) 中的一部分 |x_i-x_j| 举例化简

\sum\limits_{i=1}^n \Delta x

=|x_1-x_j|+|x_2-x_j|+\dots+|x_j-x_j|+|x_{j+1}-x_j|+\dots+|x_n-x_j|

{}

如果先将横坐标处理为递增的，很容易得知柿子 |x_j-x_j| 以前肯定是可以继续拆绝对值化简的；|x_{j+1}-x_j| 及以后的柿子是 \ge0 的，进一步化简：

=\sum\limits_{i=1}^j(x_j-x_i)+\sum\limits_{i=j+1}^n(x_i-x_j)

这玩意..

不就是前缀和嘛..？

维护有序状态下 \sum\limits_{i=1}^k x_i 和 \sum\limits_{i=1}^k y_i 的值，\sum\limits_{i=1}^j x_j 直接用 j * xj 算就行了。

--- 理理思路：读入切比雪夫意义下的坐标并化为曼哈顿意义下的坐标，因为有 $\div2$ 可能有小数，先不进行 $\div2$，最后把距离 $\div2$ 是一样的。分别对 $x_i,y_i$ 排序，处理成递增的序列和前缀和。枚举每一个终点，把它的 $x_i,y_i$ 在排好序的数组里的位置找出来（即 $x_i,y_i$ 在排序后数组里的下标），可快速算所有点到它的距离和了。 $\texttt{Code}

#include <iostream>
#include <algorithm>
#include <climits>
#include <stdio.h>
#define MAXN 100010

typedef long long i64;

int n, x[MAXN], y[MAXN], gx[MAXN], gy[MAXN];
i64 sumx[MAXN], sumy[MAXN];

inline i64 calc(int i)
{
    int rx = std::lower_bound(gx + 1, gx + n + 1, x[i]) - gx;
    int ry = std::lower_bound(gy + 1, gy + n + 1, y[i]) - gy;
    return rx * 1LL * x[i] - sumx[rx] + sumx[n] - sumx[rx] - (n - rx) * 1LL * x[i] +
        ry * 1LL * y[i] - sumy[ry] + sumy[n] - sumy[ry] - (n - ry) * 1LL * y[i];

    /*
        rx: 在 gx[] 中 x 排多少位，即 gx[i] = x 的 i
        ry: 在 gy[] 中 y 排多少位，即 gy[i] = y 的 i
        只有找到了 rx 和 ry 才能分成两步计算，rx 和 ry 也是下文两个数组下的 “j”

        dis(1, j) + dis(2, j) + ... + dis(j, j) + ... + dis(n, j) 为把 j 这个点设为终点的曼哈顿距离，坐标已经转为曼哈顿意义下的坐标
        排序后分为 j 之前和 j 之后两部分计算

        有序 x[] 下 x 坐标的贡献:
            rx 之前为 rx * x[j] - sum(x[1..j])
            rx 之后为 sum(x[j..n]) - (n - (j + 1) + 1) * x[j]

            y 坐标同理

        答案的柿子建议自己写，也可以把 * 1LL * y[i] 替换成 * 1LL * gy[ry] 
    */
}

signed main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++i)
    {
        int xi, yi;
        scanf("%d%d", &xi, &yi);
        x[i] = gx[i] = xi + yi;
        y[i] = gy[i] = xi - yi;

        /*
            转化成曼哈顿意义下坐标
            gx[] gy[] 是要经过排序得到的有序数组
            x[] y[] 存第 i 个点坐标
        */
    }

    std::sort(gx + 1, gx + n + 1);
    for(int i = 1; i <= n; ++i)
        sumx[i] = sumx[i - 1] + gx[i];

    std::sort(gy + 1, gy + n + 1);
    for(int i = 1; i <= n; ++i)
        sumy[i] = sumy[i - 1] + gy[i];

    /*
        计算前缀和
        为了维护 sum(gx[1..j]) 和 sum(gy[1..j])
        j 是文章中提到的 x_j 的下标
    */

    static i64 res = LLONG_MAX;
    for(int i = 1; i <= n; ++i)
        res = std::min(res, calc(i));

    //最后记得 div 2
    printf("%lld\n", res >> 1LL);
    return 0;
}

由于柿子比较多，很可能打错，代码中的注释有的是写代码时写的，可能和文章中的解释有些出入（主要是下标

这篇题解花了我很长时间，马上要 CPS-S 了，祝大家 RP++