[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)
