题解 | 空间跃迁-Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 城市数量
        int k = sc.nextInt(); // 跃迁半径
        
        // 读取相邻城市间的耗时（共n-1个）
        long[] a = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            a[i] = sc.nextLong();
        }
        
        // 前缀和数组：s[0] = 0，s[1] = a[0]（1→2的耗时），s[2] = a[0]+a[1]（1→3的耗时）...
        // s[x] 表示从1号城市到x+1号城市的总耗时
        long[] prefixSum = new long[n];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + a[i - 1];
        }
        
        long maxSave = 0; // 最大节省时间
        // 遍历每个城市i（1~n），计算右跳的最大节省量
        for (int i = 1; i <= n; i++) {
            int jumpTarget = Math.min(n, i + k); // 右跳目标城市（不超过n）
            if (jumpTarget > i) { // 只有跳得更远才会节省时间
                // 节省的时间 = 从i到jumpTarget的正常耗时（前缀和差值）
                long currentSave = prefixSum[jumpTarget - 1] - prefixSum[i - 1];
                if (currentSave > maxSave) {
                    maxSave = currentSave;
                }
            }
        }
        
        // 最小总耗时 = 正常总耗时 - 最大节省时间
        long minTotalTime = prefixSum[n - 1] - maxSave;
        System.out.println(minTotalTime);
        
        sc.close();
    }
}