“每日一题#17 坐标系移动 Chebyshev距离”第一次看到这个标题时我愣了一下坐标移动和切比雪夫距离放在一起葫芦里卖的什么药后来想明白了这题的灵魂其实是一个很经典的坐标变换——把坐标系旋转45度切比雪夫距离就摇身一变成为曼哈顿距离的一半。很多看起来无从下手的极值、求和问题做完这个变换后都能直接套用现成的套路。这篇就把这个技巧从头到尾拆一遍从定义、推导、代码到踩坑适合正在刷算法题、准备竞赛或者面试时遇到“距离类”题目卡壳的朋友。看完之后“点对最大距离”“点到多点距离之和最小”这两类高频题基本就能拿下。1. Chebyshev距离其实很简单1.1 定义国王一次走几步二维平面上两点A(x1,y1)、B(x2,y2)令dx|x1-x2|dy|y1-y2|切比雪夫距离的定义就是d max(dx, dy)这个定义看着抽象但配上国际象棋的国王就特别直观。国王每步可以向横、竖、斜任意方向走一格从A走到B最少需要多少步答案恰好就是max(dx, dy)。比如从(0,0)到(3,5)横差3、竖差5国王可以斜着走3步到(3,3)再竖着走2步到(3,5)总共5步。反过来竖着差了5步无论怎么斜走都无法少于5步所以答案就是5。“切比雪夫距离”这名字听起来有点唬人其实就是“来自切比雪夫的定义”在算法题里它经常以“棋盘距离”“国王距离”的身份出现。很多题目描述说“可以向八个方向移动每次移动一步”本质上就是在考切比雪夫距离。理解了这一层后面所有变换都顺理成章。1.2 三种距离放一起对比把欧氏距离、曼哈顿距离、切比雪夫距离放在一起看区别会更清晰。欧氏距离sqrt(dx² dy²)对应“直线飞行”。曼哈顿距离dx dy对应“只能横竖走街区的出租车”。切比雪夫距离max(dx, dy)对应“可以走八方向的国王”。如果你把“到原点距离不超过1”的区域画出来欧氏距离是一个圆曼哈顿距离是一个旋转45度的正方形也就是菱形切比雪夫距离是一个轴对齐的正方形。注意曼哈顿距离和切比雪夫距离的“图形”其实是旋转关系这就是后文坐标系移动的几何基础。欧氏距离无论怎么旋转都不变所以它反而不太适合用这种变换来处理真正在算法题里频繁“互化”的就是曼哈顿和切比雪夫这一对。1.3 什么时候会碰到这类题型的出现场景很固定网格上八方向移动、多个点求两两距离极值、或者棋盘类问题。直接在原坐标系里做往往要枚举所有点对O(n²)在n1e5时直接爆炸。如果题目给的是切比雪夫距离想办法把它变成曼哈顿距离就能把“二维距离”拆成两个独立的一维问题用排序、前缀和、双指针等成熟工具去处理。这就是标题里“坐标系移动”要干的事。2. 坐标系移动旋转45度之后的世界2.1 核心变换uxy, vx-y坐标系移动不是平移而是换一组基。核心变换就一行u x y v x - y用矩阵写更清楚[u] [1 1] [x] [v] [1 -1] [y]这个矩阵的行列式是-2效果等价于把坐标系旋转45度再整体缩放sqrt(2)。旋转之后原来轴对齐的正方形会变成菱形切比雪夫距离的几何形态就朝着曼哈顿距离靠过去了。为什么偏偏是xy和x-y因为要凑出一个很关键的恒等式下面单独说。2.2 距离怎么跟着变关键恒等式这个技巧的核心恒等式是max(|a|, |b|) (|ab| |a-b|) / 2对任意实数a、b都成立。验证一下a3, b-2时左边max(3,2)3右边(|1||5|)/23。没问题。回到距离。设有两个点P(x1,y1)、Q(x2,y2)令dx x2 - x1 dy y2 - y1切比雪夫距离是max(|dx|, |dy|)。做变换后du u2 - u1 (x2y2) - (x1y1) dx dy dv v2 - v1 (x2-y2) - (x1-y1) dx - dy于是|du| |dv| |dxdy| |dx-dy| 2 * max(|dx|, |dy|)所以d_切比雪夫 (|du| |dv|) / 2结论非常干净原坐标系里的切比雪夫距离等于新坐标系里的曼哈顿距离除以2。后续所有代码里最容易翻车的点就是这个“除以2”。做题时先把这个关系写在草稿纸最显眼的位置比什么都管用。2.3 反变换和那个隐藏的“同奇偶”条件反过来从(u,v)还原(x,y)x (u v) / 2 y (u - v) / 2这里藏着一个特别容易坑人的条件u和v必须同奇偶。因为uv (xy)(x-y) 2x永远是偶数所以u和v的奇偶性必然相同。如果题目要求把新坐标还原回整数坐标必须先判断同奇偶否则算出来的x、y会带小数。比如变换后得到(1, 2)u1和v2一奇一偶就不可能对应任何整数网格点。很多题里这个条件直接决定了某个候选点是否合法。2.4 从几何上理解为什么有效坐标变换的本质是“换一种方式看同一个问题”。原坐标系里切比雪夫距离对应国王走棋盘旋转45度后棋盘格变成了菱形网格国王的八方向移动等价于“先横后竖”的街区移动也就是曼哈顿距离。打个比方你站在一个每个格子都可以斜穿的广场中央去某个点需要max(dx,dy)步如果把广场旋转45度再拉伸一下会发现原本斜着走的路线全部变成横平竖直的街区路线距离数值恰好只剩原来的一半。这就是“坐标系移动”最直观的含义——距离没变是尺子变了。3. 三个高频题型从极值到求和一次讲清3.1 最大Chebyshev距离直接看极差先看最简单的高频题给定n个点求任意两点之间切比雪夫距离的最大值。遇事不决先想暴力O(n²)枚举所有点对n1000勉强能跑n1e5就彻底凉了。正确的做法是连变换都不用直接看极差答案 max( 横坐标最大值 - 横坐标最小值, 纵坐标最大值 - 纵坐标最小值 )证明也不难。任意两点切比雪夫距离等于max(|dx|,|dy|)而|dx|不可能超过横坐标总极差|dy|不可能超过纵坐标总极差所以任何点对的距离都不会超过两者中的最大值。取横坐标最大的点和横坐标最小的点它们之间的dx就是横坐标极差切比雪夫距离至少是这个值同理纵坐标极差也一定可以被某个点对达到。因此最大值就是max(两个极差)。这个结论之所以成立是因为切比雪夫距离的“极值”天然被各坐标单独控制。换成欧氏距离就没这么美了不能用这么简单的方式拆。3.2 最小化和距离松鼠聚会与前缀和最大值用极差最小值可就没这么简单了。经典题“松鼠聚会”给定n个点的坐标选其中一个点作为集合点让所有点到它的切比雪夫距离之和最小。n能到1e5O(n²)枚举中心点是肯定不行的。用坐标变换问题会立刻降维。第一步每个点(x,y)变成(uxy, vx-y)。 第二步目标函数变成sum Σ (|u_i - u_p| |v_i - v_p|) / 2除以2先放在一边不管先看怎么快速计算Σ|u_i - u_p|。这是标准的一维曼哈顿距离和把u排序做前缀和对每个候选点用二分找到它在有序数组里的位置左边贡献是u_p乘以左边个数减去左边和右边贡献是右边和减去u_p乘以右边个数。v方向完全一样。最后每个候选点的答案就是(Su Sv) / 2遍历所有原始点取最小值。这个做法的精妙之处在于切比雪夫距离本来是一个“耦合”的最大值没法拆转成曼哈顿距离后“和”就变成两个独立分量的“和”一维技巧直接上场。坐标变换的价值就在这里不是玄学而是把不可分的函数拆成了可分的函数。3.3 反着用曼哈顿距离的最大值坐标变换是双向的。反过来如果题目给的是曼哈顿距离要求所有点对距离最大值也可以用同一套变换解决。把每个点映射到(uxy, vx-y)原坐标下的曼哈顿距离|dx| |dy| max(|dxdy|, |dx-dy|) max(|du|, |dv|)这就是新坐标系下的切比雪夫距离。于是最大曼哈顿距离就等于max(u的极差, v的极差)。代码和3.1几乎一模一样只是要把坐标先变换一下。这个技巧在“求n个点两两曼哈顿距离最大值”这类题里非常实用不需要枚举点对线性复杂度就能出答案。见过不少人用最暴力的方式在O(n²)里死磕其实旋转45度后一行极差就解决了。3.4 还藏在曼哈顿MST里的同款思路再往深一层曼哈顿距离最小生成树问题里也有同一个思路的影子。经典做法是只考虑四个方向上的最近邻然后把每个方向压缩成一维扫描线问题。这里“四个方向”本质上就是坐标变换后产生的正负组合。虽然MST的代码比普通距离题复杂很多但底层逻辑仍然是“曼哈顿距离经旋转后可以用切比雪夫/四个线性组合来分解”。遇到这类题目第一反应应该是思考怎么用坐标变换降维而不是急着套生成树模板。4. 实战踩坑记录与快速排查表4.1 最容易犯的五个错这个变换写起来只有几行但真正做题时翻车点特别密集。我把自己踩过的坑和帮别人看代码时见到的坑汇总一下。第一个错忘记除以2。距离公式推导出来是切比雪夫 曼哈顿/2好多人套用曼哈顿模板后直接把SuSv当成答案结果所有输出都是正确值的两倍。尤其是题目样例给的坐标碰巧是对称的输出去居然也像模像样很容易放过去。第二个错反解坐标时不检查同奇偶。题目要求从变换后的坐标还原原坐标时一定要先判断u和v奇偶性是否一致。不一致的候选点直接跳过硬除会得到非法坐标。第三个错滥用极差。最大值可以用极差但“最小距离和”不能用极差拍脑袋必须老老实实枚举候选点。极差法只解决了“两两点对之间距离的最大值”解决不了“一个点到多个点距离的和”。第四个错溢出。坐标范围本身看着不大但uxy一层变换就可能翻倍再乘上前缀和、乘上点数很容易爆int。建议所有坐标、距离、总和全部用long long。第五个错误以为坐标必须是正数。变换对负数一样成立只要坐标是整数u、v就是整数不用另外处理负数情况。真正要注意的是反解整数条件和正负无关。4.2 排查表现象可能原因解决方法输出是正确值的两倍忘记最后除以2检查是否有“距离/2”这一步反解坐标出现小数u和v奇偶性不同先判断再执行(xy)/2最大距离用暴力超时O(n²)枚举点对改用横纵坐标极差法最小距离和结果偏大没有用前缀和而是暴力排序前缀和二分中间结果出现负数或溢出int不够全部用long long对拍小样例正确大样例错中心点选错范围确认题目要求“必须选给定点”还是“任意点”4.3 三个比较土但很有效的习惯我在实际练习中固定用三个习惯虽然土但能省下大量debug时间。第一任何带“坐标变换”的题都先把公式写在草稿纸上。不是写代码而是写“原距离 新距离 / 2”这种关系以及“u和v必须同奇偶”这种约束。写着写着思路就清晰了比盯着屏幕干想效率高得多。第二小数据暴力对拍。用随机坐标生成几个点写一个O(n²)的暴力程序算准确答案再和变换后的算法结果对一遍。变换题最容易犯“方向性”错误暴力对拍一轮就能把除以2、符号搞反这类问题全部暴露出来。第三验证变换时用一对特殊点。比如(0,0)和(3,5)切比雪夫距离是5变换后曼哈顿距离是10除以2正好是5。用一个具体数字把公式钉死后面写代码就不容易漂。5. 可以直接抄的C模板5.1 基础变换和极值函数#include bits/stdc.h using namespace std; using ll long long; struct Point { ll x, y; // 原坐标 ll u, v; // 变换后的坐标 }; // 原坐标 - 新坐标对应坐标系旋转45度 void to45(Point p) { p.u p.x p.y; p.v p.x - p.y; } // 新坐标 - 原坐标返回false表示无法还原成整数坐标 bool from45(Point p) { if ((p.u 1LL) ! (p.v 1LL)) return false; p.x (p.u p.v) / 2; p.y (p.u - p.v) / 2; return true; } // 所有点对最大切比雪夫距离极差法 ll maxChebyshev(const vectorPoint p) { ll minx LLONG_MAX, maxx LLONG_MIN; ll miny LLONG_MAX, maxy LLONG_MIN; for (auto pt : p) { minx min(minx, pt.x); maxx max(maxx, pt.x); miny min(miny, pt.y); maxy max(maxy, pt.y); } return max(maxx - minx, maxy - miny); } // 所有点对最大曼哈顿距离先旋转再用切比雪夫极差法 ll maxManhattan(const vectorPoint p) { ll minu LLONG_MAX, maxu LLONG_MIN; ll minv LLONG_MAX, maxv LLONG_MIN; for (auto pt : p) { ll u pt.x pt.y; ll v pt.x - pt.y; minu min(minu, u); maxu max(maxu, u); minv min(minv, v); maxv max(maxv, v); } return max(maxu - minu, maxv - minv); }5.2 最小距离和完整实现下面这个是“松鼠聚会”类型题的核心函数枚举每个原始点作为集合点用排序前缀和快速算出切比雪夫距离总和取最小值。// 选一个给定点作为集合点使所有点到它的切比雪夫距离之和最小 ll minSumChebyshev(vectorPoint p) { int n (int)p.size(); vectorll us(n), vs(n); // 先做坐标变换 for (int i 0; i n; i) { to45(p[i]); us[i] p[i].u; vs[i] p[i].v; } // 分别排序准备前缀和 sort(us.begin(), us.end()); sort(vs.begin(), vs.end()); vectorll preU(n 1, 0), preV(n 1, 0); for (int i 0; i n; i) { preU[i 1] preU[i] us[i]; preV[i 1] preV[i] vs[i]; } ll ans LLONG_MAX; // 枚举每一个原始点作为中心 for (int i 0; i n; i) { ll u p[i].u; ll v p[i].v; // u方向的曼哈顿距离和 int ru lower_bound(us.begin(), us.end(), u) - us.begin(); ll su u * ru - preU[ru] (preU[n] - preU[ru]) - u * (n - ru); // v方向的曼哈顿距离和 int rv lower_bound(vs.begin(), vs.end(), v) - vs.begin(); ll sv v * rv - preV[rv] (preV[n] - preV[rv]) - v * (n - rv); // 切比雪夫距离 曼哈顿距离 / 2 ans min(ans, (su sv) / 2); } return ans; }5.3 用模板时注意什么这套模板最需要注意的是“中心点的范围”。上面代码枚举的是原始点对应“集合点必须是给定点之一”的常见约束。如果题目改成“可以在任意实数点选”那就不能枚举了最优解直接取u和v的中位数本质上是两个一维中位数问题复杂度还能更低。另外(su sv) / 2这一步我直接用了整数除法。因为原坐标都是整数时任意两点变换后的曼哈顿距离一定是偶数总和也一定是偶数所以不需要担心除不尽。如果你拿到的题目坐标可能带浮点数记得改用double并小心浮点误差。还有一个小技巧如果某个候选点恰好是“所有点中u的极值点”二分出来的ru0或run-1都很正常公式里的某一侧贡献会变成0不用担心代码已经天然处理了。我个人在实际操作中的体会是这类题最难的从来不是代码而是“想到要旋转坐标系”。每次做每日一题遇到距离类问题我都会先问自己一句这个距离在旋转45度后会不会变成另一种更好算的距离只要公式写在草稿纸上把“除以2”和“同奇偶”这两个坑提前标记出来剩下的就是把模板往里套。熟练之后这条坐标变换的路子几乎可以无脑走。
Chebyshev距离与坐标系移动：旋转45度化繁为简
“每日一题#17 坐标系移动 Chebyshev距离”第一次看到这个标题时我愣了一下坐标移动和切比雪夫距离放在一起葫芦里卖的什么药后来想明白了这题的灵魂其实是一个很经典的坐标变换——把坐标系旋转45度切比雪夫距离就摇身一变成为曼哈顿距离的一半。很多看起来无从下手的极值、求和问题做完这个变换后都能直接套用现成的套路。这篇就把这个技巧从头到尾拆一遍从定义、推导、代码到踩坑适合正在刷算法题、准备竞赛或者面试时遇到“距离类”题目卡壳的朋友。看完之后“点对最大距离”“点到多点距离之和最小”这两类高频题基本就能拿下。1. Chebyshev距离其实很简单1.1 定义国王一次走几步二维平面上两点A(x1,y1)、B(x2,y2)令dx|x1-x2|dy|y1-y2|切比雪夫距离的定义就是d max(dx, dy)这个定义看着抽象但配上国际象棋的国王就特别直观。国王每步可以向横、竖、斜任意方向走一格从A走到B最少需要多少步答案恰好就是max(dx, dy)。比如从(0,0)到(3,5)横差3、竖差5国王可以斜着走3步到(3,3)再竖着走2步到(3,5)总共5步。反过来竖着差了5步无论怎么斜走都无法少于5步所以答案就是5。“切比雪夫距离”这名字听起来有点唬人其实就是“来自切比雪夫的定义”在算法题里它经常以“棋盘距离”“国王距离”的身份出现。很多题目描述说“可以向八个方向移动每次移动一步”本质上就是在考切比雪夫距离。理解了这一层后面所有变换都顺理成章。1.2 三种距离放一起对比把欧氏距离、曼哈顿距离、切比雪夫距离放在一起看区别会更清晰。欧氏距离sqrt(dx² dy²)对应“直线飞行”。曼哈顿距离dx dy对应“只能横竖走街区的出租车”。切比雪夫距离max(dx, dy)对应“可以走八方向的国王”。如果你把“到原点距离不超过1”的区域画出来欧氏距离是一个圆曼哈顿距离是一个旋转45度的正方形也就是菱形切比雪夫距离是一个轴对齐的正方形。注意曼哈顿距离和切比雪夫距离的“图形”其实是旋转关系这就是后文坐标系移动的几何基础。欧氏距离无论怎么旋转都不变所以它反而不太适合用这种变换来处理真正在算法题里频繁“互化”的就是曼哈顿和切比雪夫这一对。1.3 什么时候会碰到这类题型的出现场景很固定网格上八方向移动、多个点求两两距离极值、或者棋盘类问题。直接在原坐标系里做往往要枚举所有点对O(n²)在n1e5时直接爆炸。如果题目给的是切比雪夫距离想办法把它变成曼哈顿距离就能把“二维距离”拆成两个独立的一维问题用排序、前缀和、双指针等成熟工具去处理。这就是标题里“坐标系移动”要干的事。2. 坐标系移动旋转45度之后的世界2.1 核心变换uxy, vx-y坐标系移动不是平移而是换一组基。核心变换就一行u x y v x - y用矩阵写更清楚[u] [1 1] [x] [v] [1 -1] [y]这个矩阵的行列式是-2效果等价于把坐标系旋转45度再整体缩放sqrt(2)。旋转之后原来轴对齐的正方形会变成菱形切比雪夫距离的几何形态就朝着曼哈顿距离靠过去了。为什么偏偏是xy和x-y因为要凑出一个很关键的恒等式下面单独说。2.2 距离怎么跟着变关键恒等式这个技巧的核心恒等式是max(|a|, |b|) (|ab| |a-b|) / 2对任意实数a、b都成立。验证一下a3, b-2时左边max(3,2)3右边(|1||5|)/23。没问题。回到距离。设有两个点P(x1,y1)、Q(x2,y2)令dx x2 - x1 dy y2 - y1切比雪夫距离是max(|dx|, |dy|)。做变换后du u2 - u1 (x2y2) - (x1y1) dx dy dv v2 - v1 (x2-y2) - (x1-y1) dx - dy于是|du| |dv| |dxdy| |dx-dy| 2 * max(|dx|, |dy|)所以d_切比雪夫 (|du| |dv|) / 2结论非常干净原坐标系里的切比雪夫距离等于新坐标系里的曼哈顿距离除以2。后续所有代码里最容易翻车的点就是这个“除以2”。做题时先把这个关系写在草稿纸最显眼的位置比什么都管用。2.3 反变换和那个隐藏的“同奇偶”条件反过来从(u,v)还原(x,y)x (u v) / 2 y (u - v) / 2这里藏着一个特别容易坑人的条件u和v必须同奇偶。因为uv (xy)(x-y) 2x永远是偶数所以u和v的奇偶性必然相同。如果题目要求把新坐标还原回整数坐标必须先判断同奇偶否则算出来的x、y会带小数。比如变换后得到(1, 2)u1和v2一奇一偶就不可能对应任何整数网格点。很多题里这个条件直接决定了某个候选点是否合法。2.4 从几何上理解为什么有效坐标变换的本质是“换一种方式看同一个问题”。原坐标系里切比雪夫距离对应国王走棋盘旋转45度后棋盘格变成了菱形网格国王的八方向移动等价于“先横后竖”的街区移动也就是曼哈顿距离。打个比方你站在一个每个格子都可以斜穿的广场中央去某个点需要max(dx,dy)步如果把广场旋转45度再拉伸一下会发现原本斜着走的路线全部变成横平竖直的街区路线距离数值恰好只剩原来的一半。这就是“坐标系移动”最直观的含义——距离没变是尺子变了。3. 三个高频题型从极值到求和一次讲清3.1 最大Chebyshev距离直接看极差先看最简单的高频题给定n个点求任意两点之间切比雪夫距离的最大值。遇事不决先想暴力O(n²)枚举所有点对n1000勉强能跑n1e5就彻底凉了。正确的做法是连变换都不用直接看极差答案 max( 横坐标最大值 - 横坐标最小值, 纵坐标最大值 - 纵坐标最小值 )证明也不难。任意两点切比雪夫距离等于max(|dx|,|dy|)而|dx|不可能超过横坐标总极差|dy|不可能超过纵坐标总极差所以任何点对的距离都不会超过两者中的最大值。取横坐标最大的点和横坐标最小的点它们之间的dx就是横坐标极差切比雪夫距离至少是这个值同理纵坐标极差也一定可以被某个点对达到。因此最大值就是max(两个极差)。这个结论之所以成立是因为切比雪夫距离的“极值”天然被各坐标单独控制。换成欧氏距离就没这么美了不能用这么简单的方式拆。3.2 最小化和距离松鼠聚会与前缀和最大值用极差最小值可就没这么简单了。经典题“松鼠聚会”给定n个点的坐标选其中一个点作为集合点让所有点到它的切比雪夫距离之和最小。n能到1e5O(n²)枚举中心点是肯定不行的。用坐标变换问题会立刻降维。第一步每个点(x,y)变成(uxy, vx-y)。 第二步目标函数变成sum Σ (|u_i - u_p| |v_i - v_p|) / 2除以2先放在一边不管先看怎么快速计算Σ|u_i - u_p|。这是标准的一维曼哈顿距离和把u排序做前缀和对每个候选点用二分找到它在有序数组里的位置左边贡献是u_p乘以左边个数减去左边和右边贡献是右边和减去u_p乘以右边个数。v方向完全一样。最后每个候选点的答案就是(Su Sv) / 2遍历所有原始点取最小值。这个做法的精妙之处在于切比雪夫距离本来是一个“耦合”的最大值没法拆转成曼哈顿距离后“和”就变成两个独立分量的“和”一维技巧直接上场。坐标变换的价值就在这里不是玄学而是把不可分的函数拆成了可分的函数。3.3 反着用曼哈顿距离的最大值坐标变换是双向的。反过来如果题目给的是曼哈顿距离要求所有点对距离最大值也可以用同一套变换解决。把每个点映射到(uxy, vx-y)原坐标下的曼哈顿距离|dx| |dy| max(|dxdy|, |dx-dy|) max(|du|, |dv|)这就是新坐标系下的切比雪夫距离。于是最大曼哈顿距离就等于max(u的极差, v的极差)。代码和3.1几乎一模一样只是要把坐标先变换一下。这个技巧在“求n个点两两曼哈顿距离最大值”这类题里非常实用不需要枚举点对线性复杂度就能出答案。见过不少人用最暴力的方式在O(n²)里死磕其实旋转45度后一行极差就解决了。3.4 还藏在曼哈顿MST里的同款思路再往深一层曼哈顿距离最小生成树问题里也有同一个思路的影子。经典做法是只考虑四个方向上的最近邻然后把每个方向压缩成一维扫描线问题。这里“四个方向”本质上就是坐标变换后产生的正负组合。虽然MST的代码比普通距离题复杂很多但底层逻辑仍然是“曼哈顿距离经旋转后可以用切比雪夫/四个线性组合来分解”。遇到这类题目第一反应应该是思考怎么用坐标变换降维而不是急着套生成树模板。4. 实战踩坑记录与快速排查表4.1 最容易犯的五个错这个变换写起来只有几行但真正做题时翻车点特别密集。我把自己踩过的坑和帮别人看代码时见到的坑汇总一下。第一个错忘记除以2。距离公式推导出来是切比雪夫 曼哈顿/2好多人套用曼哈顿模板后直接把SuSv当成答案结果所有输出都是正确值的两倍。尤其是题目样例给的坐标碰巧是对称的输出去居然也像模像样很容易放过去。第二个错反解坐标时不检查同奇偶。题目要求从变换后的坐标还原原坐标时一定要先判断u和v奇偶性是否一致。不一致的候选点直接跳过硬除会得到非法坐标。第三个错滥用极差。最大值可以用极差但“最小距离和”不能用极差拍脑袋必须老老实实枚举候选点。极差法只解决了“两两点对之间距离的最大值”解决不了“一个点到多个点距离的和”。第四个错溢出。坐标范围本身看着不大但uxy一层变换就可能翻倍再乘上前缀和、乘上点数很容易爆int。建议所有坐标、距离、总和全部用long long。第五个错误以为坐标必须是正数。变换对负数一样成立只要坐标是整数u、v就是整数不用另外处理负数情况。真正要注意的是反解整数条件和正负无关。4.2 排查表现象可能原因解决方法输出是正确值的两倍忘记最后除以2检查是否有“距离/2”这一步反解坐标出现小数u和v奇偶性不同先判断再执行(xy)/2最大距离用暴力超时O(n²)枚举点对改用横纵坐标极差法最小距离和结果偏大没有用前缀和而是暴力排序前缀和二分中间结果出现负数或溢出int不够全部用long long对拍小样例正确大样例错中心点选错范围确认题目要求“必须选给定点”还是“任意点”4.3 三个比较土但很有效的习惯我在实际练习中固定用三个习惯虽然土但能省下大量debug时间。第一任何带“坐标变换”的题都先把公式写在草稿纸上。不是写代码而是写“原距离 新距离 / 2”这种关系以及“u和v必须同奇偶”这种约束。写着写着思路就清晰了比盯着屏幕干想效率高得多。第二小数据暴力对拍。用随机坐标生成几个点写一个O(n²)的暴力程序算准确答案再和变换后的算法结果对一遍。变换题最容易犯“方向性”错误暴力对拍一轮就能把除以2、符号搞反这类问题全部暴露出来。第三验证变换时用一对特殊点。比如(0,0)和(3,5)切比雪夫距离是5变换后曼哈顿距离是10除以2正好是5。用一个具体数字把公式钉死后面写代码就不容易漂。5. 可以直接抄的C模板5.1 基础变换和极值函数#include bits/stdc.h using namespace std; using ll long long; struct Point { ll x, y; // 原坐标 ll u, v; // 变换后的坐标 }; // 原坐标 - 新坐标对应坐标系旋转45度 void to45(Point p) { p.u p.x p.y; p.v p.x - p.y; } // 新坐标 - 原坐标返回false表示无法还原成整数坐标 bool from45(Point p) { if ((p.u 1LL) ! (p.v 1LL)) return false; p.x (p.u p.v) / 2; p.y (p.u - p.v) / 2; return true; } // 所有点对最大切比雪夫距离极差法 ll maxChebyshev(const vectorPoint p) { ll minx LLONG_MAX, maxx LLONG_MIN; ll miny LLONG_MAX, maxy LLONG_MIN; for (auto pt : p) { minx min(minx, pt.x); maxx max(maxx, pt.x); miny min(miny, pt.y); maxy max(maxy, pt.y); } return max(maxx - minx, maxy - miny); } // 所有点对最大曼哈顿距离先旋转再用切比雪夫极差法 ll maxManhattan(const vectorPoint p) { ll minu LLONG_MAX, maxu LLONG_MIN; ll minv LLONG_MAX, maxv LLONG_MIN; for (auto pt : p) { ll u pt.x pt.y; ll v pt.x - pt.y; minu min(minu, u); maxu max(maxu, u); minv min(minv, v); maxv max(maxv, v); } return max(maxu - minu, maxv - minv); }5.2 最小距离和完整实现下面这个是“松鼠聚会”类型题的核心函数枚举每个原始点作为集合点用排序前缀和快速算出切比雪夫距离总和取最小值。// 选一个给定点作为集合点使所有点到它的切比雪夫距离之和最小 ll minSumChebyshev(vectorPoint p) { int n (int)p.size(); vectorll us(n), vs(n); // 先做坐标变换 for (int i 0; i n; i) { to45(p[i]); us[i] p[i].u; vs[i] p[i].v; } // 分别排序准备前缀和 sort(us.begin(), us.end()); sort(vs.begin(), vs.end()); vectorll preU(n 1, 0), preV(n 1, 0); for (int i 0; i n; i) { preU[i 1] preU[i] us[i]; preV[i 1] preV[i] vs[i]; } ll ans LLONG_MAX; // 枚举每一个原始点作为中心 for (int i 0; i n; i) { ll u p[i].u; ll v p[i].v; // u方向的曼哈顿距离和 int ru lower_bound(us.begin(), us.end(), u) - us.begin(); ll su u * ru - preU[ru] (preU[n] - preU[ru]) - u * (n - ru); // v方向的曼哈顿距离和 int rv lower_bound(vs.begin(), vs.end(), v) - vs.begin(); ll sv v * rv - preV[rv] (preV[n] - preV[rv]) - v * (n - rv); // 切比雪夫距离 曼哈顿距离 / 2 ans min(ans, (su sv) / 2); } return ans; }5.3 用模板时注意什么这套模板最需要注意的是“中心点的范围”。上面代码枚举的是原始点对应“集合点必须是给定点之一”的常见约束。如果题目改成“可以在任意实数点选”那就不能枚举了最优解直接取u和v的中位数本质上是两个一维中位数问题复杂度还能更低。另外(su sv) / 2这一步我直接用了整数除法。因为原坐标都是整数时任意两点变换后的曼哈顿距离一定是偶数总和也一定是偶数所以不需要担心除不尽。如果你拿到的题目坐标可能带浮点数记得改用double并小心浮点误差。还有一个小技巧如果某个候选点恰好是“所有点中u的极值点”二分出来的ru0或run-1都很正常公式里的某一侧贡献会变成0不用担心代码已经天然处理了。我个人在实际操作中的体会是这类题最难的从来不是代码而是“想到要旋转坐标系”。每次做每日一题遇到距离类问题我都会先问自己一句这个距离在旋转45度后会不会变成另一种更好算的距离只要公式写在草稿纸上把“除以2”和“同奇偶”这两个坑提前标记出来剩下的就是把模板往里套。熟练之后这条坐标变换的路子几乎可以无脑走。
