C. Closest Cities 题解

1. 题意重述

在数轴上有 $n$ 个城市，坐标依次为 $a_1 < a_2 < \dots < a_n$。保证对于每个城市，其“最近的城市”是唯一的（即不存在等距的最近邻居）。

旅行规则：

• 从城市 $x$ 到任意城市 $y$，花费为两点间的距离 $|a_x - a_y|$ 枚硬币；
• 从城市 $x$ 到其最近的城市，花费固定为 $1$ 枚硬币。

给出 $m$ 个询问，每次给定起点 $x$ 和终点 $y$，求最少花费。

2. 关键观察

由于所有城市都在一条数轴上，且移动可以在任意两点间跳转，直觉上最优路径可能不会“回头”。事实上可以证明：对于任何 $x < y$，最优路径一定是一直向右移动，每次要么直接走到下一个城市，要么利用“到最近城市”的便宜移动（如果最近城市恰好在右侧）；向左移动同理。因此，从 $x$ 到 $y$ 的最小花费等于将路径分解为一系列相邻城市间的移动，每段选择最便宜的走法，并将花费累加。

定义 $cost(i \to i+1)$ 为从城市 $i$ 走到 $i+1$ 的最小硬币数。根据规则：

• 如果城市 $i$ 的最近城市是 $i+1$（即 $a_{i+1}-a_i \le a_i - a_{i-1}$），则我们可以利用 $1$ 硬币的“最近移动”直接从 $i$ 跳到 $i+1$，因此 $cost(i \to i+1) = 1$。
• 否则，城市 $i$ 的最近城市是 $i-1$，那么从 $i$ 到 $i+1$ 没有任何优惠，只能花费距离 $a_{i+1} - a_i$ 枚硬币走过去。

同理可以定义向左走的相邻花费 $cost(i \to i-1)$。

3. 预处理前缀和

为了方便回答任意区间查询，我们构建两个前缀和数组：

• $R[i]$：从城市 $1$ 出发，一直向右走到城市 $i+1$ 的累计最小花费（即 $\sum_{k=1}^{i} cost(k \to k+1)$）。
• $L[i]$：从城市 $n$ 出发，一直向左走到城市 $i-1$ 的累计最小花费（即 $\sum_{k=i}^{n-1} cost(k+1 \to k)$）。

具体计算时，我们可以先判断每个城市（除了两端）的最近邻居方向：

char type(const vector<int>& a, int id) {
    int distL = (id == 0 ? INF : a[id] - a[id - 1]);
    int distR = (id + 1 == a.size() ? INF : a[id + 1] - a[id]);
    if (distL < distR) return 'L';   // 最近城市在左边
    if (distL > distR) return 'R';   // 最近城市在右边
    assert(false); // 根据题意不会出现相等
}

然后，对于 $i$ 从 $1$ 到 $n-1$，若 $type(i-1) = \text{'R'}$，则 $R[i] = R[i-1] + 1$，否则 $R[i] = R[i-1] + (a_i - a_{i-1})$。

同理，对于 $i$ 从 $n-2$ 到 $0$，若 $type(i+1) = \text{'L'}$，则 $L[i] = L[i+1] + 1$，否则 $L[i] = L[i+1] + (a_{i+1} - a_i)$。

4. 回答查询

• 若 $x < y$（向右走），则最小花费为 $R[y-1] - R[x-1]$。这里 $R$ 数组下标对应关系：$R[i]$ 表示从城市 $1$ 走到 $i+1$ 的花费。因此从 $x$ 走到 $y$ 的花费就是前 $y-1$ 步的花费减去前 $x-1$ 步的花费。
• 若 $x > y$（向左走），则最小花费为 $L[y] - L[x]$。$L[i]$ 表示从城市 $n$ 走到 $i-1$ 的花费，因此从 $x$ 走到 $y$（$x>y$）的花费就是从 $n$ 走到 $y-1$ 的花费减去从 $n$ 走到 $x-1$ 的花费。

注意代码中城市下标从 $0$ 开始，因此读入的 $x,y$ 需要减一。

5. 复杂度分析

• 预处理：判断每个城市的类型 $O(1)$，计算前缀和 $O(n)$。
• 每个询问：$O(1)$ 查表差分。
• 总体时间复杂度：$O(n + m)$ 每个测试用例，满足 $\sum n,\sum m \le 10^5$ 的限制。
• 空间复杂度：$O(n)$ 存储坐标和前缀和数组。

6. 完整代码（带注释）

#include <bits/stdc++.h>
using namespace std;

const int INF = 1'000'000'009;

// 判断城市 id 的最近邻居方向
char type(const vector<int>& a, int id) {
    int distL = (id == 0 ? INF : a[id] - a[id - 1]);
    int distR = (id + 1 == a.size() ? INF : a[id + 1] - a[id]);
    if (distL < distR) return 'L';
    if (distL > distR) return 'R';
    assert(false); // 题目保证唯一性
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        
        // R[i] : 从城市 1 走到城市 i+1 的最小花费 (i 从 1 到 n-1)
        // L[i] : 从城市 n 走到城市 i-1 的最小花费 (i 从 n-2 到 0)
        vector<int> R(n), L(n);
        for (int i = 1; i < n; ++i) {
            // 前一个城市 i-1 的最近邻居如果在右侧，则到 i 花 1 硬币
            int cost = (type(a, i - 1) == 'R') ? 1 : (a[i] - a[i - 1]);
            R[i] = R[i - 1] + cost;
        }
        for (int i = n - 2; i >= 0; --i) {
            // 后一个城市 i+1 的最近邻居如果在左侧，则从 i+1 到 i 花 1 硬币
            int cost = (type(a, i + 1) == 'L') ? 1 : (a[i + 1] - a[i]);
            L[i] = L[i + 1] + cost;
        }
        
        int m;
        cin >> m;
        while (m--) {
            int x, y;
            cin >> x >> y;
            --x; --y;   // 转换为 0-based 下标
            if (x < y) {
                // 向右走：从 x 到 y 的花费 = 从 1 到 y 的花费 - 从 1 到 x 的花费
                cout << R[y] - R[x] << '\n';
            } else {
                // 向左走：从 x 到 y 的花费 = 从 n 到 y 的花费 - 从 n 到 x 的花费
                cout << L[y] - L[x] << '\n';
            }
        }
    }
    return 0;
}

7. 总结

本题巧妙地将图上的最短路径问题转化为数轴上相邻城市间的局部决策问题。通过预处理两个方向的前缀和，可以在 $O(1)$ 时间内回答每个询问。关键在于认识到最优路径一定是单调移动的，从而可以使用差分前缀和技巧。