题解 P5638 【【CSGRound2】光骓者的荣耀】

· · 题解

前言

让我们一起赞美良心的出题人吧！

题目背景

小K又在做白日梦了。他进入到他的幻想中，发现他打下了一片江山。

题目描述

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

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

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

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

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

解法：

用前缀和记录，再贪心找出区间k的最大值就可以惹QwQ（因为传送器只能用一次）

时间复杂度：O(n)

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],k,num[1000005],ans;
//十年OI……（我们要开long long
inline long long read(){//读入优化
    long long f=1,out=0;char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        out*=10;out+=c-'0';
        c=getchar();
    }
    return f*out;
}
int main(){
    n=read(),k=read();//题面所给
    for(long long i=1;i<=n-1;i++)//读入
        a[i]=read();
    for(long long i=1;i<=n-1;i++)//前缀和记录
        num[i]=num[i-1]+a[i];
    if(k)//如果用不了传送器，就不记录
    for(long long i=k;i<=n-1;i++){
        ans=max(ans,num[i]-num[i-k]);
    }
    cout<<num[n-1]-ans;//总和减去找到的最大值就是答案
    return 0;
}