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

· · 题解

这道题要使时间少,就要使传送的时间多。题目就转化成了要找k个连续的区间,使区间的和尽可能的大。

暴力找和的时间复杂度为o(k(n-k)) 当n=1000000,k=500000时,就会tle

由于是找区间和,我们很快就想到了用一维前缀和来优化。

一维前缀和讲解(会的可以跳过这部分,直接去看代码了)

前缀和的思路就是s[i]表示sum{a[j]}(0<=j<=i)

比如,以下这个数组的前缀和是

  0 1 2
a:1 2 3
s:1 3 6

前缀和的求法

s[0]=a[0],s[i]=s[i-1]+a[i];

求区间和(l,r)

s[r]-s[l-1]

//s[r]表示从0到i-1的前缀和,s[l-1]表示从0到l-1的前缀和。减去s[l-1]就去掉了0~l-1之内的所有数。剩下的就是区间和了。

前缀和讲解完毕,接下来就看代码。

#include<iostream>
using namespace std;
long long a[10000005],s[10000005];
long long max(long long a,long long b){
    return a>b?a:b;
}
int main(){
    long long n,m,k,i,sum=0,Max=0;
    cin>>n>>k;
    for(i=1;i<n;++i){ //为了方便,不初始化s[0]=a[0],就从1开始数组。反正a[0]未赋值全局变量默认是0,0+a[1]就是a[1]。
        scanf("%lld",a+i);
        s[i]+=s[i-1]+a[i]; //求前缀和。
    }
    Max=0;
    for(i=k;i<n;++i){
        Max=max(Max,s[i]-s[i-k]);//求(区间和的)最大值
    }
    cout<<s[n-1]-Max; //和-最大值就是最终所需要的时间。
    return 0;
}