interestingLSY 的博客

interestingLSY 的博客

题解 P3964 【[TJOI2013]松鼠聚会】

posted on 2018-02-27 22:42:12 | under 题解 |

[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

没错就点个赞(逃