🔍 问题核心

题目给定一条由 $N$ 个城市按顺序连接而成的路径图。城市 $i$ 和 $i+1$ 之间有一条边。定义图的直径为所有城市对之间的最短距离的最大值。

目标是在图中添加一条新边 $R_{\text{new}}$（其长度为两端点的曼哈顿距离），使得新图的直径尽可能小。

💡 关键思路

添加一条边后，新图的直径可能由以下两种情况决定：

1. 原路径上某段未被新边“缩短”的距离。
2. 经过新边的某条路径。

因此，我们需要选择最优的边，使得上述两种情况中的最大值最小。

一种常见的解法思路是考虑直径的单调性，并尝试最小化所有点对之间的最大距离。

🧮 算法步骤

1. 预处理距离：

   • 计算每个城市 $i$ 到城市 $1$ 的路径距离 $dist1[i]$。
   • 计算每个城市 $i$ 到城市 $N$ 的路径距离 $distN[i]$。

2. 寻找候选点对：

   • 一个经典结论是，最优的新边往往连接那些在原路径上距离较远，但曼哈顿距离较近的点对。这是因为曼哈顿距离决定了新边的长度，而原路径距离决定了不经过新边时的最远距离。

3. 计算新图直径：

   • 对于候选点对 $(a, b)$，新边的长度 $d = |X_a - X_b| + |Y_a - Y_b|$。
   • 添加新边后，两点间距离变为 $d$。新图的直径需要考虑所有点对通过新边所能缩短的最大距离。一个常见的公式是，新直径可能为：$$\max \left( \text{原路径上某段距离}, \ \min(dist1[a] + d + distN[b], \ dist1[b] + d + distN[a]) \right) $$
   • 我们需要最小化这个最大值。

4. 优化技巧：

   • 直接枚举所有点对是 $O(N^2)$，对于 $N \leq 2.5 \times 10^5$ 不可行。
   • 可以利用曼哈顿距离的性质（例如，通过坐标变换）或单调队列/二分答案来优化寻找候选点对的过程。

✅ 结论

该问题的核心在于巧妙地选择新边，以最大程度地“缩短”原图中最远的点对距离。通过预处理、利用距离性质和优化技巧，可以在合理时间内找到最优解。