【题解】[USACO04OPEN] Cave Cows 3

平面内有 \(n\) 个点 \((x_i,y_i)\),两点间距离定义为曼哈顿距离,即 \(|x_1-x_2|+|y_1-y_2|\) 。

求所有点对中,距离最大值为多少。

原范围:\(n\le 50000\)。

提示1:绝对值不好整,想想办法

提示2:也可以使用经典套路:曼哈顿转切比雪夫


Solution 1

因为 \(|x_1-x_2|+|y_1-y_2|\) 中的绝对值不好办,所以对它对分类讨论。

不妨令 \(x_1<x_2\),则

  1. \(y_1<y_2\) ,则 \(dis=(x_2+y_2)-(x_1+y_1)\)。

  2. \(y_1>y_2\) ,则 \(dis=(x_2-y_2)-(x_1-y_1)\)。

所以,我们只需要求 \(x_i+y_i\) 和 \(x_i-y_i\) 的 \(max/min\) 即可,最终答案为

\[max\{max\{x_i+y_i\}-min\{x_i+y_i\}~~,~~max\{x_i-y_i\}-min\{x_i-y_i\}\} \]

时间复杂度 \(O(n)\)。

Solution 2

曼哈顿距离与切比雪夫距离及其相互转化 - 自为风月马前卒

原定的点 \((x,y)\rightarrow(x+y,x-y)\) 后,曼哈顿距离就等于之后的切比雪夫距离。

即从 \(|x_1-x_2|+|y_1-y_2|\) 变成了 \(max\{|(x_1+y_1)-(x_2+y_2)|~~,~~|(x_1-y_1)+(x_2-y_2)|\}\)。

这个式子显然等价于Solution 1中的式子,时间复杂度 \(O(n)\) 即可计算。

上一篇:Basic数据占位符定义


下一篇:Text数据占位符定义