题解 | 空间跃迁

容易让人红温的就是这个城市为n个，城市之间耗时为n-1个了，下标处理逻辑理解起来真的想锤人。

需要弄懂自己设计的summ[n]到底是什么意义：前缀和，表示从城市1到城市i的距离，那么设立summ[0]就是城市1到城市1距离，

summ[n-1]即为城市1到城市n的距离

因此，求解穿梭城市省下来的时间，就等于城市1到城市i+k的用时tb - 城市1到城市i的用时ta，根据前面理解，就终于知道应该用summ[i+k - 1] - summ[i - 1]表示省下来的时间

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,k;
    cin >> n >> k;
    vector<long long> summ(n, 0); 
    // summ[0]表示从城市1到城市1的距离，summ[1]是城市1到城市2的距离，summ[n-1]城市1到城市n距离
    long long temp;
    // vector<long long> a(n-1);
    for (int i = 1; i < n; i++) {
        cin >> temp;
        summ[i] = summ[i-1] + temp;
    }
    long long total_cost = summ[n-1];
    if (k == 0 || n <= k) {
        cout << total_cost << '\n';
        return 0;
    }
    long long max_save = 0;
    long long current_save = 0;
    for (int i = 1; i <= n - k; i++) { // 城市之间的用时，n-1段
        current_save = summ[i + k - 1] - summ[i - 1]; // 城市1到城市i+k的距离-城市1到i城距离
        max_save = max(current_save, max_save);
    }
    cout << total_cost - max_save << '\n';
    return 0;
}
// 64 位输出请用 printf("%lld")