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

· · 题解

这是比赛的第一题（然而我感觉比第二题难）

由于小K的不稳定传送器只能传送一次，可以想到用总时间-传送节约的跑的时间

因为总距离是变不了的，所以说求出传送节约时间的最大值即可求出最短需要的时间

如果一个一个枚举的相隔k的城市之间的时间的话，会很慢，于是想到用一个求区间和的好东西：前缀和

前缀和通常用sum[ ]表示，sum[i]表示从1到i之间的总和（这里就是从1跑到i所需的时间），用前缀和求从a地跑到b地所需的时间，求sum[b]-sum[a]即可

这样，找出相距k的点之间跑的时间的最大值就用一遍for就可以过了

并且用前缀和的话，sum[n]就是所要求的总距离

于是问题就解决了

上代码！

#include<iostream>
using namespace std;
long long sum[1000001];//因为有10^12的a，所以用long long
int main()
{
    long long n,k,a,maxx=0;
    cin>>n>>k;
    sum[1]=0;
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        sum[i]=sum[i-1]+a;//算前缀和
    }
    for(int i=k+1;i<=n;i++)//这里从1到n-k，下面用sum[i+k]-sum[i]也可以
        maxx=max(maxx,sum[i]-sum[i-k]);
    cout<<sum[n]-maxx;
    return 0;
}

我的思路是比较容易想到的思路，没有大佬们的那么快，但是能过。如果想要更快的代码就去看看大佬们代码的吧

（蒟蒻第一次写题解，可能会有些错误，欢迎指出；叙述可能不太清晰，请多多包容）