题解 P3964 【[TJOI2013]松鼠聚会】
interestingLSY
2018-02-27 22:42:12
# [TJOI2013]松鼠聚会 题解 by LSY
先说一句，本题解中所有 $\Delta X , \Delta Y$ 都指横纵坐标之差的**绝对值**。
本题主要思路：
- 将切比雪夫距离转换为曼哈顿距离
- 对式子进行变形，得到前缀和的形式
- 依照变形完的式子，编写代码
## ① 好奇怪的距离啊
**知道题中的距离为“切比雪夫距离”的 dalao 可以跳过这一部分**
可以发现题中有一个 Interesting 的地方：
```
两个点的距离定义为点 (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, $ Dis = \Delta Y $ . 对于图2, $ Dis = \Delta X $ 。（想想为啥）
也就是说 $ Dis = max( \Delta X , \Delta Y)$。
这个距离又叫做**切比雪夫距离**。
再回去看一眼题：
**题意说白了不就“是给你n个点，选一个点使得这个点到其他所有点的切比雪夫距离之和最小”嘛！**
然而呢...
这样做的话，假设当前枚举的点为点 $i$ , 则**当前**答案为：
$$ \sum_{k=1}^n \ qdis(k,i)$$
（ $qdis(k,i)$表示 $k,i$ 两点的切比雪夫距离）
复杂度 $O(n^2)$ ,毫无疑问一定会 GG。
## ② 知道是切比雪夫距离又能怎样？
先介绍一下**曼哈顿距离**：
$$ Dis = \Delta X + \Delta Y $$
**OI常用套路:将一个点 $(x,y)$ 的坐标变为 $(x+y,x-y)$ 后，原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离。（想想为啥）**
**反过来，将一个点 $(x,y)$ 的坐标变为 $(\frac{x+y}{2},\frac{x-y}{2})$ 后，原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离！**
这样我们就可以通过坐标变换，将切比雪夫距离转为曼哈顿距离。
## ③ 转成曼哈顿距离又如何？
转换成为曼哈顿距离后，假设当前枚举的点为点 $i$ ，则**当前**答案为：
$$ \sum_{k=1}^n \ Mdis(k,i)$$
（ $Mdis(k,i)$表示 $k,i$两点的曼哈顿距离）
骗人啊，不都差不多吗，不也是 $O(n^2)$？
别着急，我们一步步推。
$$ \sum_{k=1}^n \ Mdis(k,i)$$
$$=Mdis(1,i)+Mdis(2,i)+Mdis(3,i)+...+Mdis(n,i)$$
$$=\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....事情开始变得有趣.....有点**前缀和**的意思.....
别忘了本题解中所有 $ \Delta X , \Delta Y$ 都指横纵坐标之差的**绝对值**，那么就会有两种情况。（就拿 $Y$ 这边来说吧, $X$这边类似。~~我比较懒就不打了~~）
假定现在各个点的 $Y$是有序的，那么
$$\Delta Y(1,i) + \Delta Y(2,i) + ... +\Delta Y(n,i)$$
$$=|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)$。
## ④ 真正的复杂度？
坐标变换：$O(n)$
前缀和处理：$O(n)$
枚举每个点：$O(n)$
计算一个点的答案：$O(\log n)$
总复杂度：$O(n \cdot \log n)$
log 的来源：排序、lower_bound
## ⑤ Code：
这里只列出关键部分：
为了防止爆 `long long`，某些地方使用 `unsigned long long`，即 `ull`。
```cpp
#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。
~~没错就点个赞（逃~~