题解原因

这篇题解旨在帮助理解，dalao请忽视。

因为这是一道红题红题，所以我在这里讲述的详细一点。

题目简介

有 𝑛n 个城市，每两个城市之间有双向通路，耗费时间 𝑎𝑖ai​ (其实可以理解为长度为 𝑎𝑖ai​ ) ，小K从 1−𝑛1−n 走访 (可以理解为从1走到 n )。

但是小K可以从第 𝑖i 个城市直接跳转到第 𝑖−𝑘i−k 或 𝑖+𝑘i+k 。(只可使用一次)

注意：他可以不访问所有的城市，使用传送器不耗费时间 (这句话意味着上面的跳转方案的思路是正确的，比如我完全可以从城市 1 跳到城市 4 ，只要使小K走过的总长度最短就可以)

求最快的用时 (即求最短的走路长度)。

思路分析

结合样例，我们可以发现，我们最终走过的长度就是总长度-跳转的长度总长度-跳转的长度，输入的 𝑘k 即为我们跳转的范围。

总长度使一个固定值，即所有路径的长度和。

那么要使得最终走过的长度最短，只需使跳转的长度最大。

我们只需要在所给的 𝑎𝑖ai​ 中选取 𝑘k 个数，使得 ∑𝑖=𝑥𝑥+𝑘𝑎𝑖i=x∑x+k​ai​ 的值最大即可。

我们可以枚举每一个 𝑘k 的范围，求 ∑ ，在这里放一份实现代码：

for (int i = 1; i <= n; i++) {
	long long ans2 = 0;
	for (int j = 0; j < k; j++) {
		ans2 += cxk[i + j];
	}
	maxx = max(maxx, ans2);
}

但是我们会发现这个毒瘤数据范围（注意看21~25）

显然这样循环会重复计算中间的一些值，21~25都会超时。

那么我们怎么优化呢？

优化

我们可以在循环的基础上，去掉重复计算的值。

在从 𝑎1a1​ 到 𝑎𝑘ak​ 求和的基础上，加上第 𝑎𝑘+1ak+1​ 个数，减去 𝑎1a1​ ，是不是就可以去掉重复计算的值了？ 依然取其最大，我们可以这样写：

a = 0, b = a + k;
for (int i = a; i < b; i++)
	ans2 += cxk[i];
for (int i = 1; i <= n - k; i++) {
	ans2 = ans2 + cxk[b] - cxk[a];
	maxx = max(maxx, ans2);
	a++, b++;
}

当然输出时应该输出总长度-跳转的长度，

cout << ans - maxx;

这就是核心代码了，最后把 头文件及初始化一写：

#include <bits/stdc++.h>
using namespace std;
int n, k, a, b;
long long cxk[1000010], ans, maxx, ans2;

数据读入：

ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n - 1; i++)
   cin >> cxk[i], ans += cxk[i];

最后

return 0;