题解：CF1922C Closest Cities

MhxMa · 2024-01-20 19:35:28 · 题解

题意

题目给出了一些城市在数轴上的坐标，城市之间的距离是它们坐标之差的绝对值。对于每个城市，定义最近的城市为与其距离最小的城市。可以进行两种操作：花费城市间的距离个硬币旅行，或者花费 1 个硬币旅行到最近的城市。给定多个查询，每个查询包含两个城市，要求计算从一个城市到另一个城市的最小花费。

思路

对于每个城市，预处理出到它左边和右边最近的城市的距离，可以用两个数组分别存储在 pre 和 suff。然后对于每个查询，判断目标城市在起始城市的左边还是右边，分别输出对应的最小花费。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);

        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        int m;
        cin >> m;
        vector<pair<int, int>> queries;

        while (m--) {
            int a, b;
            cin >> a >> b;
            queries.push_back({a, b});
        }

        vector<int> pre(n), suff(n);

        pre[0] = 0;
        pre[1] = 1;

        for (int i = 2; i < n; i++) {
            pre[i] = (abs(arr[i - 1] - arr[i - 2]) > abs(arr[i - 1] - arr[i])) ?
                        pre[i - 1] + 1 :
                        pre[i - 1] + abs(arr[i - 1] - arr[i]);
        }

        suff[n - 1] = 0;
        suff[n - 2] = 1;

        for (int i = n - 3; i >= 0; i--) {
            suff[i] = (abs(arr[i + 1] - arr[i]) > abs(arr[i + 1] - arr[i + 2])) ?
                        suff[i + 1] + abs(arr[i + 1] - arr[i]) :
                        suff[i + 1] + 1;
        }

        for (auto& q : queries) {
            int x = q.first;
            int y = q.second;

            if (x < y) {
                cout << pre[y - 1] - pre[x - 1] << "\n";
            } else {
                cout << suff[y - 1] - suff[x - 1] << "\n";
            }
        }
    }

    return 0;
}