选择配送

知识点 曼哈顿距离/绝对值处理

时间限制: 2.000 Sec 内存限制: 512 MB

题目描述

在一个二维平面城市中，有 n 个客户，第 i(1≤i≤n) 个客户的位置坐标为 (xi,yi)。快递侠需要在 m 个候选配送站中选择一个作为自己的起始点，第 j(1≤j≤m) 个配送站的坐标为 (aj,bj)。快递侠在城市中移动时，只能沿水平或垂直方向走，因此两点之间的距离为曼哈顿距离，即对于两点 (p1,q1)和 (p2,q2)，距离定义为 ∣p1−p2∣+∣q1−q2∣。
快递侠希望选择一个配送站，使得他到最远的客户的距离（即到所有客户的曼哈顿距离的最大值）尽可能小。请你帮助快递侠计算出这个最小的最大距离是多少。

输入

第一行一个整数 T(1≤T≤10⁶)，表示测试数据组数。
第一行包含两个整数 n 和 m，分别表示客户数量和候选配送站数量。
接下来 n 行，每行包含两个整数 xi,yi(1≤xi,yi≤10⁹)，表示第 i 个客户的位置坐标。
接下来 m 行，每行包含两个整数 ai,bi(1≤ai,bi≤10⁹)，表示第 i 个候选配送站的位置坐标。
保证所有测试数据的 n 之和与 m 之和均不超过 10⁶。

输出

对于每组测试数据，输出一行一个整数，表示快递侠选择最优配送站后，到所有客户的曼哈顿距离的最大值的最小值。

样例输入 Copy

2
2 2
1 2
2 1
1 1
2 2
3 2
1 1
2 2
3 3
1 1
2 2

样例输出 Copy

1
2

题解和代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        ll p1max = -1e18, p1min = 1e18;
        ll p2max = -1e18, p2min = 1e18;
        for(int i = 0; i < n; i++){
            ll x, y;
            cin >> x >> y;
            ll p1 = x + y;
            ll p2 = x - y;
            p1max = max(p1max, p1);
            p1min = min(p1min, p1);
            p2max = max(p2max, p2);
            p2min = min(p2min, p2);
        }
        ll ans = 1e18;
        for(int j = 0; j < m; j++){
            ll a, b;
            cin >> a >> b;
            ll s1 = a + b;
            ll s2 = a - b;
            ll d = max({
                llabs(s1 - p1max),
                llabs(s1 - p1min),
                llabs(s2 - p2max),
                llabs(s2 - p2min)
            });
            ans = min(ans, d);
        }
        cout << ans << "\n";
    }
    return 0;
}

这道题的核心在于曼哈顿距离的数学性质转换。1

曼哈顿距离的数学转换

曼哈顿距离定义为：|x₁-x₂| + |y₁-y₂|

通过数学变换，这个表达式可以重写为：

|x₁-x₂| + |y₁-y₂| = max(|(x₁+y₁)-(x₂+y₂)|, |(x₁-y₁)-(x₂-y₂)|)

这个等式可以通过分类讨论四种情况来证明：

1. x₁≥x₂, y₁≥y₂

2. x₁≥x₂, y₁≤y₂

3. x₁≤x₂, y₁≥y₂

4. x₁≤x₂, y₁≤y₂

算法步骤详解

1. 坐标转换

对每个客户点(x,y)，我们计算两个新的坐标值：

• p₁ = x+y (在45°方向上的投影)

• p₂ = x-y (在135°方向上的投影)

ll p1 = x + y;
ll p2 = x - y;

2. 计算极值

找出所有客户点这两个新坐标的最大最小值：

p1max = max(p1max, p1);  // x+y 的最大值
p1min = min(p1min, p1);  // x+y 的最小值
p2max = max(p2max, p2);  // x-y 的最大值
p2min = min(p2min, p2);  // x-y 的最小值

3. 计算每个配送站的最远距离

对于每个配送站(a,b)：

ll s1 = a + b;  // 配送站的 x+y 值
ll s2 = a - b;  // 配送站的 x-y 值

以下四个值中的最大者就是该配送站到最远客户的曼哈顿距离：

• |s₁-p₁max|：配送站到 x+y 最大值客户的距离

• |s₁-p₁min|：配送站到 x+y 最小值客户的距离

• |s₂-p₂max|：配送站到 x-y 最大值客户的距离

• |s₂-p₂min|：配送站到 x-y 最小值客户的距离

ll d = max({
    llabs(s1 - p1max),
    llabs(s1 - p1min),
    llabs(s2 - p2max),
    llabs(s2 - p2min)
});

4. 更新答案

在所有配送站中，找到最小的最远距离：

ans = min(ans, d);

为什么这种方法有效？

从几何角度看，曼哈顿距离可以看作是在旋转45°的坐标系下的L∞范数（切比雪夫距离）。通过坐标变换，我们将问题转化为在这个旋转坐标系下找最优点。

在这个变换后的坐标系中，所有客户点形成一个矩形区域（由p₁min、p₁max、p₂min、p₂max定义）。任意点到这个矩形的最大距离一定是到矩形四个顶点之一的距离。

这种方法将时间复杂度从朴素解法的O(n*m)优化到了O(n+m)，其中n是客户数，m是配送站数。