P5638

题目

题目描述：

小 K 打下的江山一共有 nn 个城市，城市 ii 和城市 i+1i+1 有一条双向高速公路连接，走这条路要耗费时间 aia_i。

小 K 为了关心人民生活，决定定期进行走访。他每一次会从 11 号城市到 nn 号城市并在经过的城市进行访问。其中终点必须为城市 nn。

不仅如此，他还有一个传送器，传送半径为 kk，也就是可以传送到 i−ki-k 和 i+ki+k。如果目标城市编号小于 11 则为 11，大于 nn 则为 nn。

但是他的传送器电量不足，只能传送一次，况且由于一些原因，他想尽量快的完成访问，于是就想问交通部部长您最快的时间是多少。

注意：他可以不访问所有的城市，使用传送器不耗费时间。

输入格式：

两行，第一行两个正整数 n,kn,k。

第二行 n−1n-1 个整数，第 ii 个表示 aia_i。

输出格式：

一个整数，表示答案。

数据范围与说明：

样例解释 1：

样例 1,2 的图示均为以下图片：

不使用传送器直接走，答案为 66，可以证明这个是最小值。

样例解释 2：

在 33 处使用，传送到 44，答案为 33，可以证明这个是最小值。

数据范围：

对于所有数据，n≥2n\ge 2，k≥1k\ge 1，ai>0a_i > 0。

测试点编号 nn 的范围 kk 的范围 aia_i 的范围
1∼101\sim 10 ≤100\le 100 ≤100\le 100 ≤105\le 10^5
11∼2011\sim 20 ≤3×103\le 3\times 10^3 ≤3×103\le 3\times 10^3 ≤109\le 10^9
2121 ≤105\le 10^5 ≤105\le 10^5 ≤1012\le 10^{12}
2222 ≤2×105\le 2\times 10^5 ≤2×105\le 2\times 10^5 ≤1012\le 10^{12}
2323 ≤5×105\le 5\times 10^5 ≤5×105\le 5\times 10^5 ≤1012\le 10^{12}
24∼2524\sim 25 ≤106\le 10^6 ≤106\le 10^6 ≤1012\le 10^{12}

输入输出样例 #1

输入：

1
2
4 0
1 2 3

输出：

1
6

输入输出样例 #2

输入：

1
2
4 1
1 2 3

输出：

1
3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll a[N],s[N];
int main(){
    ll n,k;
    cin>>n>>k;
    if(k+1>=n){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n-1;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    ll ans=LLONG_MAX;
    for(int i=1;i<=n-k;i++){
        ll sum = s[i + k - 1] - s[i - 1];
        ans=min(ans,s[n-1]-sum);
    }
    cout<<ans;
    return 0;
}