题解 | #空间跃迁#

题目链接

题目描述

有 $n$ 个城市排成一列，从城市 $i$ 到城市 $i+1$ 的耗时为 $a_i$ 。可以从 1 号城市出发到 $n$ 号城市，途中可以使用一次空间跃迁。空间跃迁的半径为 $k$ ，即可以从第 $i$ 个城市无时间消耗地传送到第 $i-k$ 或第 $i+k$ 个城市。求从 1 号城市到 $n$ 号城市的最小总耗时。

解题思路

本题的目标是找到一条从城市 1 到城市 $n$ 的路径，该路径包含一次空间跃迁，使得总耗时最小。

我们可以将整个行程分为三段：

从城市 1 走到城市 $i$ 。
从城市 $i$ 空间跃迁到城市 $j$ （其中 $j=i-k$ 或 $j=i+k$ ）。
从城市 $j$ 走到城市 $n$ 。

总耗时 = (从 1 到 $i$ 的耗时) + (从 $j$ 到 $n$ 的耗时)。空间跃迁本身不耗时。

为了快速计算任意两城市间的行走耗时，我们可以使用前缀和。定义一个前缀和数组 $s$ ，其中 $s[i]$ 表示从城市 1 走到城市 $i+1$ 的总耗时，即 $s[i] = \sum_{p=1}^{i} a_p$ 。那么，从城市 $u$ 走到城市 $v$ （假设 $u < v$ ）的耗时就可以通过 $s[v-1] - s[u-1]$ 计算得出。

我们的策略是遍历所有可能的跃迁点。假设我们从城市 $i$ 进行空间跃迁，目的地是城市 $j$ 。那么总耗时就是从城市 1 走到城市 $i$ 的时间，加上从城市 $j$ 走到城市 $n$ 的时间。

我们需要枚举所有可能的出发城市 $i$ （ $1 \le i \le n$ ），对于每个 $i$ ，计算两种可能的跃迁：

向前跃迁：跃迁到城市 $j = i+k$ 。
- 条件： $1 \le i < j \le n$ 。
- 耗时：(1走到 $i$ ) + ( $j$ 走到 $n$ ) = $(s[i-1] - s[0]) + (s[n-1] - s[j-1])$ 。
向后跃迁：跃迁到城市 $j = i-k$ 。
- 条件： $1 \le j < i \le n$ 。
- 耗时：(1走到 $j$ ) + ( $i$ 走到 $n$ ) = $(s[j-1] - s[0]) + (s[n-1] - s[i-1])$ 。
- 注意，向后跃迁等价于从城市 $j$ 出发，跃迁到城市 $i$ 。因此，我们只需要考虑向前跃迁，即从一个城市 $i$ 跃迁到 $i+k$ ，就可以覆盖所有情况，避免重复计算。

因此，我们的最终策略是：

计算出路径耗时的前缀和数组 $s$ 。
不使用空间跃迁的总耗时为 $s[n-1]$ ，将其作为初始的最小耗时。
遍历所有可能的跃迁出发点 $i$ (从 1 到 $n-k$ )。对于每个 $i$ ，计算从 $i$ 跃迁到 $i+k$ 的总耗时：
- 总耗时 = (从 1 走到 $i$ 的耗时) + (从 $i+k$ 走到 $n$ 的耗时)。
- 这相当于省去了从 $i$ 走到 $i+k$ 的路程。
- 节省的时间 = $\sum_{p=i}^{i+k-1} a_p = s[i+k-1] - s[i-1]$ 。
- 跃迁后的总耗时 = (不跃迁的总耗时) - (节省的时间) = $s[n-1] - (s[i+k-1] - s[i-1])$ 。
在所有可能的跃迁方案中取一个最小的总耗时，即为最终答案。

我们需要找到能节省最多时间的跃迁区间 $[i, i+k]$ 。也就是找到一个 $i$ ，使得 $s[i+k-1] - s[i-1]$ 最大。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    cin >> n >> k;

    // 前缀和数组，s[i] 表示从城市1到城市i+1的耗时
    vector<long long> s(n, 0);
    if (n > 1) {
        vector<long long> a(n - 1);
        for (int i = 0; i < n - 1; ++i) {
            cin >> a[i];
        }

        s[1] = a[0];
        for (int i = 1; i < n - 1; ++i) {
            s[i + 1] = s[i] + a[i];
        }
    }

    // 不使用空间跃迁的总耗时
    long long total_cost = s[n - 1];
    
    // 如果 k=0 或者 n <= k，无法进行有效的向前跃迁，只能走完全程
    if (k == 0 || n <= k) {
        cout << total_cost << "\n";
        return 0;
    }

    long long min_cost = total_cost;

    // 遍历所有可能的跃迁区间 [i, i+k]
    // i 是城市编号，从 1 到 n-k
    // 对应到前缀和数组下标是 i-1
    for (int i = 1; i <= n - k; ++i) {
        // 从城市 i 走到 i+k 的耗时
        long long saved_cost = s[i + k - 1] - s[i - 1];
        min_cost = min(min_cost, total_cost - saved_cost);
    }
    
    cout << min_cost << "\n";

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        
        // 前缀和数组，s[i] 表示从城市1到城市i+1的耗时
        long[] s = new long[n];
        if (n > 1) {
            long[] a = new long[n - 1];
            for (int i = 0; i < n - 1; i++) {
                a[i] = sc.nextLong();
            }

            s[1] = a[0];
            for (int i = 1; i < n - 1; i++) {
                s[i + 1] = s[i] + a[i];
            }
        }
        
        // 不使用空间跃迁的总耗时
        long totalCost = s[n - 1];
        
        // 如果 k=0 或者 n <= k，无法进行有效的向前跃迁，只能走完全程
        if (k == 0 || n <= k) {
            System.out.println(totalCost);
            return;
        }

        long minCost = totalCost;

        // 遍历所有可能的跃迁区间 [i, i+k]
        // i 是城市编号，从 1 到 n-k
        for (int i = 1; i <= n - k; i++) {
            // 从城市 i 走到 i+k 的耗时
            long savedCost = s[i + (int)k - 1] - s[i - 1];
            minCost = Math.min(minCost, totalCost - savedCost);
        }

        System.out.println(minCost);
    }
}

import sys

def solve():
    n, k = map(int, sys.stdin.readline().split())
    
    if n > 1:
        a = list(map(int, sys.stdin.readline().split()))
    else:
        a = []

    # 前缀和数组，s[i] 表示从城市1到城市i+1的耗时
    s = [0] * n
    if n > 1:
        s[1] = a[0]
        for i in range(1, n - 1):
            s[i + 1] = s[i] + a[i]
            
    # 不使用空间跃迁的总耗时
    total_cost = s[n - 1]
    
    # 如果 k=0 或者 n <= k，无法进行有效的向前跃迁，只能走完全程
    if k == 0 or n <= k:
        print(total_cost)
        return

    min_cost = total_cost

    # 遍历所有可能的跃迁区间 [i, i+k]
    # i 是城市编号，从 1 到 n-k
    for i in range(1, n - k + 1):
        # 从城市 i 走到 i+k 的耗时
        saved_cost = s[i + k - 1] - s[i - 1]
        min_cost = min(min_cost, total_cost - saved_cost)
        
    print(min_cost)

solve()

算法及复杂度

算法：前缀和、枚举
时间复杂度：计算前缀和数组需要 $O(n)$ 的时间，遍历所有可能的跃迁方案需要 $O(n-k)$ 的时间。因此，总时间复杂度为 $O(n)$ 。
空间复杂度：需要一个数组来存储前缀和，因此空间复杂度为 $O(n)$ 。