P3964 [TJOI2013]松鼠聚会 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • interestingLSY
    log2的由来: 在有序的Y数组中二分查找当前点的坐标! 我比较懒就用了stl::lower_bound
  • attack
    写的真好,赞赞赞
  • 幸济蒸馒头
    %%%%%
  • 我_膜法师_蒟蒻
    orz
  • cellur925
    写的真好,赞赞赞
  • ROY1994
    请问dalao为什么该坐标时不 /2 但是最后除二呢 @interestingLSY
  • ROY1994
    @interestingLSY
  • 1517460958dyc
    楼上的,您想出小数吗?
  • Christopher_Yan
    赞赞赞
  • bjrjk
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
作者: interestingLSY  更新时间: 2018-02-27 22:42  在Ta的博客查看 举报    60  

[TJOI2013]松鼠聚会 题解 by LSY

先说一句,本题解中所有 $\color{Blue} \Delta X , \Delta Y$ 都指横纵坐标之差的绝对值


①好奇怪的距离啊

知道题中的距离为“切比雪夫距离”的dalao可以跳过这一部分

可以发现题中有一个Interes♂ting的地方:

两个点的距离定义为点 (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

这是什么意思?我们画图看看。

对于图1, $\color{Blue} Dis = \Delta Y $ . 对于图2, $\color{Blue} Dis = \Delta X $ (想想为啥?)

也就是说 $\color{Blue} Dis = max( \Delta X , \Delta Y)$

这个距离又叫做切比雪夫距离

再回去看一眼题:

题意说白了不就“是给你n个点,选一个点使得这个点到其他所有点的切比雪夫距离之和最小”嘛!

然而呢...

这样做的话,假设当前枚举的点为点 $i$ , 则当前答案为:

$$\color{Red} \sum_{k=1}^n \ qdis(k,i)$$ . . . ( $qdis(k,i)$表示 $k,i$两点的切比雪夫距离)

复杂度 $O(n^2)$ ,毫无疑问一定会 $GG$


②知道是切比雪夫距离又能怎样?

先介绍一下曼哈顿距离:

$$\color{Blue} Dis = \Delta X + \Delta Y$$

OI常用套路:将一个点 $\color{Blue}(x,y)$ 的坐标变为 $\color{Blue}(x+y,x-y)$ 后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离(想想为啥?)

反过来,将一个点 $\color{Blue}(x,y)$ 的坐标变为 $\color{Blue}(\frac{x+y}{2},\frac{x-y}{2})$ 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离!

这样我们就可以通过坐标变换,将切比雪夫距离转为曼哈顿距离。


③转成曼哈顿距离又如何?

转换成为曼哈顿距离后,假设当前枚举的点为点 $i$ , 则当前答案为:

$$\color{Red} \sum_{k=1}^n \ Mdis(k,i)$$ . . . ( $Mdis(k,i)$表示 $k,i$两点的曼哈顿距离)

骗人啊,不都差不多吗,不也是 $O(n^2)$?

别着急,我们一步步推。

$$\color{Red} \sum_{k=1}^n \ Mdis(k,i)$$

$$\color{Red}=Mdis(1,i)+Mdis(2,i)+Mdis(3,i)+...+Mdis(n,i)$$

$$\color{Red}=\Delta X(1,i)+\Delta Y(1,i) + \Delta X(2,i)+\Delta Y(2,i) + ... + \Delta X(n,i)+\Delta Y(n,i)$$

$$\color{Green}=\lgroup \Delta X(1,i)+\Delta X(2,i)+...+\Delta X(n,i) \rgroup + \color{Blue}\lgroup \Delta Y(1,i) + \Delta Y(2,i) + ... +\Delta Y(n,i) \rgroup $$

emmmmmm....事情开始变得有趣.....有点前缀和的意思.....

别忘了本题解中所有 $\color{Blue} \Delta X , \Delta Y$ 都指横纵坐标之差的绝对值,那么就会有两种情况。(就拿 $\color{Blue}Y$ 这边来说吧, $\color{Green}X$这边类似。我比较懒就不打了

假定现在各个点的 $\color{Blue}Y$是有序的,那么

$$\color{Blue}\Delta Y(1,i) + \Delta Y(2,i) + ... +\Delta Y(n,i)$$

$$\color{Blue}=|Y_i-Y_1|+|Y_i-Y_2|+...+|Y_i-Y_n|$$

$$\color{Blue}=(Y_i-Y_1)+(Y_i-Y_2)+...+(Y_i-Y_i) \quad + \quad$$

$$\color{Red}(Y_{i+1}-Y_i)+(Y_{i+2}-Y_i)+...+(Y_n-Y_i)$$

$$\color{Blue}=(i \cdot Y_i\ -\ \sum_{k=1}^i Y_k) \quad + \quad \color{Red}(\sum_{k=i+1}^n Y_k\ -\ (n-i) \cdot Y_i)$$

再定睛一看,是不是可以用前缀和来维护!

这样计算一次的复杂度...就会大大降低,至少不用 $O(n)$


④真正的复杂度?

坐标变换: $\color{Blue}O(n)$

前缀和处理: $\color{Blue}O(n)$

枚举每个点: $\color{Blue}O(n)$

计算一个点的答案: $\color{Blue}O(log_2n)$

总复杂度: $\color{Red}O(n \cdot log_2n)$

仔细想想这个log哪来的,答案会在评论区里ovo


⑤Code:

这里只列出关键部分: 为了防止爆 $long\ long$, 某些地方使用 $unsigned\ long\ long$, 即 $ull$

#define For(i,j) for( rg int (i) = 1 ; (i) <= (j) ; (i)++ )
#define For0(i,j) for( rg int (i) = 0 ; (i) < (j) ; (i)++ )
/////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////
#define MAXN 100010

int n;
ll x[MAXN], y[MAXN];
ll inpx[MAXN], inpy[MAXN];
ll sumx[MAXN], sumy[MAXN];
ull ans = ULONG_LONG_MAX;

il void Getsum(){
    sumx[0] = sumy[0] = 0;
    For(i,n){
        sumx[i] = sumx[i-1] + x[i];
        sumy[i] = sumy[i-1] + y[i];
    }
}
il ull Try( int u ){
    ull ansx = 0 , ansy = 0;

    int xpos = lower_bound(x+1,x+1+n,inpx[u]) - x;
    ansx += xpos*inpx[u] - sumx[xpos];
    ansx += sumx[n] - sumx[xpos] - (n-xpos)*inpx[u];

    int ypos = lower_bound(y+1,y+1+n,inpy[u]) - y;
    ansy += ypos*inpy[u] - sumy[ypos];
    ansy += sumy[n] - sumy[ypos] - (n-ypos)*inpy[u];

    return ansx + ansy;
}

int main(){
    Read(n);
    For(i,n){
        ll a,b;
        Read(a,b);
        x[i] = inpx[i] = a+b;
        y[i] = inpy[i] = a-b;
    }

    sort(x+1,x+1+n);
    sort(y+1,y+1+n);
    Getsum();

    For(i,n){
        ull tans = Try(i);
        Mymin(ans,tans);
    }
    printf("%llu\n",ans >> 1LL);

    return 0;
}

⑥没听懂?

没事,随便问吧

私信我或者在评论区中留言均可(但留言要@我0v0)

如果发现错误,请务必指出0v0

没错就点个赞(逃

评论

  • Happynewyear
    前排
  • Happynewyear
    %%%
  • Light_Tracing
    真详细, 辛苦了
  • _Qer
    前排%%%
  • yu__xuan
    %%%
作者: Rem° 更新时间: 2019-11-11 21:53  在Ta的博客查看 举报    6  

一道有趣的题OwO

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


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

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

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

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

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

在平面几何中,若二点 pq 的直角坐标系坐标为 $(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 算就行了。

$dis(i,j)$ 的另一部分 $\Delta y$ 可同理化简求值。


理理思路:

读入 切比雪夫 意义下的坐标并化为 曼哈顿 意义下的坐标,因为有 $\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++

评论

  • cellur925
    偶遇学长%%%
  • 星之ζ泪殇
    orz
作者: HiJ1m 更新时间: 2017-11-30 20:59  在Ta的博客查看 举报    6  

我的博客原文链接:http://www.cnblogs.com/Elfish/p/7931766.html

本题两点间的距离是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=0,t=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*t; 
} 
struct Node{
    long long X,Y; 
}a[MAXN]; 
int N,x[MAXN],y[MAXN],pos;
long long ans=1ll<<62,s1[MAXN],s2[MAXN];
int main()
{
    N=read();
    for(int i=1;i<=N;i++){
        int p=read(),q=read();
        x[i]=a[i].X=p+q;
        y[i]=a[i].Y=p-q;
    }
    sort(x+1,x+N+1);
    sort(y+1,y+N+1);
    for(int i=1;i<=N;i++)
        s1[i]=s1[i-1]+x[i],
        s2[i]=s2[i-1]+y[i];
    for(int i=1;i<=N;i++){
        long long tmp=0;
        pos=lower_bound(x+1,x+N+1,a[i].X)-x;
        tmp+=s1[N]-s1[pos]-a[i].X*(N-pos)+a[i].X*pos-s1[pos];
        pos=lower_bound(y+1,y+N+1,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/2);
    return 0;
}

评论

  • 还没有评论
作者: Heartlessly 更新时间: 2019-06-10 21:51  在Ta的博客查看 举报    3  

Description

给定 $n$ 个点,每个点的坐标为 $(x_i,y_i)$,且点 $(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$ 。现要找到一个点,使其它点到这个点的距离和最小,输出这个最小值。

$(0 \leq n \leq 10^5,-10^9 \leq x_i,y_i \leq 10^9)$

Solution

很容易看出这道题属于 切比雪夫距离 的一般模型。即对于两个点 $(x_1, y_1),(x_2,y_2)$,它们之间的距离为 $$ \max(\left | x_1 - x_2\right | , \left | y_1 - y_2\right | ) $$ 直接求 切比雪夫距离 似乎很困难?考虑把 切比雪夫距离 转化为 曼哈顿距离,即把每个点的坐标 $(x,y)$ 变为 $(\frac{x + y}{2}, \frac{x - y}{2})$ 。(不会的请学习 常用距离算法详解

枚举所选的点 $i$,我们只需要计算其它点到它的曼哈顿距离和即可。

如果某个点 $j$ 的横坐标 $x_j \leq x_i$,则它的对总距离的贡献为 $x_i - x_j$,反之则为 $x_j - x_i$ 。

这样就可以分两种情况讨论了。

设前 $k$ 个点的横坐标都 $\leq x_i$,那么所有点横坐标的贡献和为

ZnGuuV.png

对于 $\sum\limits_{i = 1}^k x_i$ 和 $\sum\limits_{i = k + 1}^n x_i$,我们可以预处理出 $x$ 的前缀和后 $O(1)$ 求得。

怎么求 $k$ 呢?显然可以将横坐标排序后二分得到。

纵坐标 $y$ 的计算方法与上面一样。时间复杂度为 $O(n \log n)$ 。

切比雪夫距离 转成 曼哈顿距离 时要除以 $2$,为了避免出现小数,我们可以横坐标和纵坐标同时乘上 $2$,最后答案除以 $2$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e5;
int n, x[MAXN + 5], y[MAXN + 5], p[MAXN + 5], q[MAXN + 5];
LL ans = 0x7fffffffffffffff, prex[MAXN + 5], prey[MAXN + 5];

int main() {
    read(n);
    for (int a, b, i = 1; i <= n; ++i) {
        read(a), read(b);
        x[i] = p[i] = a + b, y[i] = q[i] = a - b;//转曼哈顿距离,且乘上 2 
    }
    sort(p + 1, p + n + 1), sort(q + 1, q + n + 1);//排序 
    for (int a, b, i = 1; i <= n; ++i)//维护前缀和 
        prex[i] = prex[i - 1] + p[i], prey[i] = prey[i - 1] + q[i];
    for (int posx, posy, i = 1; i <= n; ++i) {
        posx = lower_bound(p + 1, p + n + 1, x[i]) - p;
        posy = lower_bound(q + 1, q + n + 1, y[i]) - q;
        //二分找到 x[i] 和 y[i] 是所有点中第几个大的 
        LL sumx, sumy;
        sumx = (LL) posx * x[i] - prex[posx] + 
        prex[n] - prex[posx] - (LL) (n - posx) * x[i];//计算横坐标贡献 
        sumy = (LL) posy * y[i] - prey[posy] + 
        prey[n] - prey[posy] - (LL) (n - posy) * y[i];//计算纵坐标贡献 
        ans = min(ans, sumx + sumy);
    }
    write(ans / 2);//答案不要忘记除回去 
    putchar('\n');
    return 0;
}

评论

  • interestingLSY
    %%%
  • bztMinamoto
    卧槽你居然还活着
作者: quantum11 更新时间: 2018-12-04 15:30  在Ta的博客查看 举报    3  

题意为给定一些点,选其中一个点使其他点到这个点的切比雪夫距离之和最小,求出最小距离。

切比雪夫距离=$\max(\Delta x,\Delta y)$,因为取$max$不太好优化,我们可以把它转化为曼哈顿距离$(\Delta x+\Delta y)$来做。

将$(x,y)$变为$(\frac{x+y}2,\frac{x−y}2)$ 后,原坐标系中的切比雪夫距离$=$新坐标系中的曼哈顿距离

将$(x,y)$变为$(x+y,x−y)$后,原坐标系中的曼哈顿距离$=$新坐标系中的切比雪夫距离

如果$x,y$数组都是有序的,那么

$$ans_x=\sum ^{n}_{j=1}\Delta(j,i)$$

$$=\Delta x(1,i)+\Delta x(2,i)+\Delta x(3,i)+...+\Delta x(n,i)$$

$$=(x_i-x_1)+(x_i-x_2)+...+(x_i-x_{i-1})+(x_{i+1}-x_i)+(x_{i+2}-x_i)+(x_n-x_i)$$

$$=\sum_{j=1}^{i-1}(x_i-x_j)+\sum_{j=i+1}^n(x_j-x_i)$$

$$=\sum_{j=1}^n x_j-2\times\sum_{j=1}^i x_j-x_i\times(n-2\times i)$$

然后就用前缀和优化一下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;
    return x*f;
}
struct A{ll x,y;}a[N];ll x[N],y[N],s1[N],s2[N],ans=1ll<<62;int n,p,u,v;
int main(){
    n=read();
    for(int i=1;i<=n;++i) u=read(),v=read(),a[i].x=x[i]=u+v,a[i].y=y[i]=u-v;
    sort(x+1,x+n+1);sort(y+1,y+n+1);
    for(int i=1;i<=n;++i) s1[i]=s1[i-1]+x[i],s2[i]=s2[i-1]+y[i];
    for(int i=1;i<=n;++i){
        ll tmp=0;
        p=lower_bound(x+1,x+n+1,a[i].x)-x;tmp+=s1[n]-2*s1[p]-a[i].x*(n-2*p);
        p=lower_bound(y+1,y+n+1,a[i].y)-y;tmp+=s2[n]-2*s2[p]-a[i].y*(n-2*p);
        ans=min(ans,tmp);
    }return !printf("%lld",ans>>1);
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。