【题目来源】
https://www.luogu.com.cn/problem/P5638

【题目描述】
小 K 又在做白日梦了。他进入到他的幻想中，发现他打下了一片江山。
小 K 打下的江山一共有 n 个城市，城市 i 和城市 i+1 有一条双向高速公路连接，走这条路要耗费时间 ai。
小 K 为了关心人民生活，决定定期进行走访。他每一次会从 1 号城市到 n 号城市并在经过的城市进行访问。其中终点必须为城市 n。
不仅如此，他还有一个传送器，传送半径为 k，也就是可以传送到 i−k 和 i+k。如果目标城市编号小于 1 则为 1，大于 n 则为 n。但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。
注意：他可以不访问所有的城市，使用传送器不耗费时间。

【输入格式】
两行，第一行 n, k。
第二行 n−1 个整数，第 i 个表示 ai。

【输出格式】
一个整数，表示答案。

【输入样例1】
4 0
1 2 3

【输出样例1】
6

【输入样例2】
4 1
1 2 3

【输出样例2】
3

【数据范围】
n≤10^6，k≤10^6，0≤ai≤10^12

【算法分析】
● 一维前缀和：https://blog.csdn.net/hnjzsyjyj/article/details/144635240
（一）什么是一维前缀和？
一维前缀和非常简单，简单到一句话就能说清楚。即，一个长度为 n 的一维数组 a[1]~a[n]，其一维前缀和 s[i]=a[1]+a[2]+...+a[i]。这么简单？需要专门学？需要，因为利用前缀和可以提高计算效率，不学就想不到。
（二）一维前缀和，通常用于快速计算 [le, ri] 中数据的“区间和”。
利用“一维前缀和”，快速计算 [le, ri] 中数据的“区间和”的步骤为：
（1）利用给定的数据，预处理出一个“前缀和数组 sum[i]”。
方法一：将给定的数据以 a[i] 读入 → cin>>a[i], sum[i]=sum[i-1]+a[i]   （1≤i≤n）
方法二：将给定的数据以 sum[i] 读入 → cin>>sum[i], sum[i]+=sum[i-1]   （1≤i≤n）
（2）通过查表“前缀和数组”，快速计算位于 [le, ri] 中数据的“区间和”：sum[ri]-sum[le-1]   （ri≥le）。同理，利用“一维前缀和”高效计算长度为 k 的区间和的公式为：sum[i]-sum[i-k]
可见，一维前缀和能够把时间复杂度为 O(n) 的区间计算优化为 O(1) 的端点计算。

● 一维差分：
（1）构建一维差分数组
一个下标从 1 开始的一维数组的各元素 a[1]~a[n]，其对应的一维差分数组的定义为 d[i]=a[i]-a[i-1]（1 ≤ i ≤ n）。即，一维差分数组是原数组相邻元素的差。
显然，根据一维差分数组的定义，可知：
d[i]=a[i]-a[i-1]，d[i-1]=a[i-1]-a[i-2]，...，d[2]=a[2]-a[1]，d[1]=a[1]-a[0]
进而推出 a[i] = d[1] + d[2] + ... + d[i]，所以“差分是前缀和的逆运算”。
（2）区间操作转端点操作 d[le]+=x，d[ri+1]-=x 大大提升算法效率
求证：通过执行 d[le]+=x，d[ri+1]-=x 这两个操作，能够实现对原数组 [le,ri] 区间内每个元素都加上 x，而区间外的元素值保持不变。
证明：由一维差分数组定义 d[i]=a[i]-a[i-1]，可知 a[i]=d[i]+a[i-1]。显然：
若 i=le，则 a[le]=d[le]+a[le-1]。那么 d[le]+=x，必然导致原数组中从 le 开始的每个元素都加上了 x；
若 i=ri+1，则 a[ri+1]=d[ri+1]+a[ri]。那么 d[ri+1]-=x，必然导致原数组中从 ri+1 开始的每个元素都减去了 x；
综上，可得证。
注意：此处的原数组及差分数组的下标都从1开始。

● 由于 i 为城市编号，k 为传送器的传送半径，则 i+k 表示传送到第 i+k 个城市。例如，若 i=2，k=1，则 i+k=2+1=3，表示传送到第 3 个城市。

● 本题首先利用给定的 n-1 个耗费时间 ai 构建前缀和数组 s[]，然后对前缀和数组 s[] 的每一个元素构建传送半径为 k 的差分数组。在这个过程中，特别要注意城市编号 i 与前缀和数组中的元素差分时下标的对应关系 s[i+k-1]-s[i-1]。如下图所示。

例如，基于上图可知，若城市下标为 2，传送半径为 3，则有 s[i+k-1]-s[i-1]=s[2+3-1]-s[2-1]=s[4]-s[1]=a[2]+a[3]+a[4]。

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn=1e6+5;
LL s[maxn],d[maxn];
LL t;
int n,k;int main() {cin>>n>>k;for(int i=1; i<n; i++) {cin>>s[i];s[i]+=s[i-1];}for(int i=1; i<=n-k; i++) {t=max(t,s[i+k-1]-s[i-1]);}cout<<s[n-1]-t<<endl;return 0;
}/*
in:
4 1
1 2 3out:
3
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/144885387
https://www.luogu.com.cn/problem/solution/P5638
https://www.lanqiao.cn/problems/2128/learning/