BGN58: 空间跃迁

思路

有 个城市排成一条线，相邻城市之间有行走耗时。你从城市 1 出发要到城市 ，中途可以使用一次空间跃迁，半径为 ，也就是从城市 瞬间跳到城市 或 （不花时间）。

先想一下：如果不用跃迁，总耗时就是所有相邻城市之间耗时的总和。用了跃迁之后呢？从城市 跳到城市 ，相当于跳过了从 到 这一段连续 条边的费用。往回跳到 没有意义，因为我们最终还是要往前走。

所以问题就变成了：在 条边中，找一段连续 条边，使得它们的费用之和最大，然后从总费用中减去这个最大值。

这不就是经典的滑动窗口嘛！维护一个大小为 的窗口，滑过去找最大的窗口和就行了。

特殊情况： 时没法跃迁，直接输出总和。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, r;
    scanf("%d%d", &n, &r);
    vector<long long> cost(n - 1);
    long long total = 0;
    for(int i = 0; i < n - 1; i++){
        scanf("%lld", &cost[i]);
        total += cost[i];
    }
    if(r == 0){
        printf("%lld\n", total);
        return 0;
    }
    long long windowSum = 0;
    for(int i = 0; i < r; i++){
        windowSum += cost[i];
    }
    long long maxSkip = windowSum;
    for(int i = r; i < n - 1; i++){
        windowSum += cost[i] - cost[i - r];
        maxSkip = max(maxSkip, windowSum);
    }
    printf("%lld\n", total - maxSkip);
    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();
        int r = sc.nextInt();
        long[] cost = new long[n - 1];
        long total = 0;
        for (int i = 0; i < n - 1; i++) {
            cost[i] = sc.nextLong();
            total += cost[i];
        }
        if (r == 0) {
            System.out.println(total);
            return;
        }
        long windowSum = 0;
        for (int i = 0; i < r; i++) {
            windowSum += cost[i];
        }
        long maxSkip = windowSum;
        for (int i = r; i < n - 1; i++) {
            windowSum += cost[i] - cost[i - r];
            maxSkip = Math.max(maxSkip, windowSum);
        }
        System.out.println(total - maxSkip);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, r = map(int, input().split())
    cost = list(map(int, input().split()))
    total = sum(cost)
    if r == 0:
        print(total)
        return
    window_sum = sum(cost[:r])
    max_skip = window_sum
    for i in range(r, n - 1):
        window_sum += cost[i] - cost[i - r]
        if window_sum > max_skip:
            max_skip = window_sum
    print(total - max_skip)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const [n, r] = lines[0].split(' ').map(Number);
    const cost = lines[1].split(' ').map(Number);
    let total = 0;
    for (let i = 0; i < n - 1; i++) total += cost[i];
    if (r === 0) {
        console.log(total);
        return;
    }
    let windowSum = 0;
    for (let i = 0; i < r; i++) windowSum += cost[i];
    let maxSkip = windowSum;
    for (let i = r; i < n - 1; i++) {
        windowSum += cost[i] - cost[i - r];
        if (windowSum > maxSkip) maxSkip = windowSum;
    }
    console.log(total - maxSkip);
});

复杂度分析

  • 时间复杂度：，一次遍历求总和，一次滑动窗口。
  • 空间复杂度：，存储费用数组。