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

· · 题解

题解：CSG Round2 T1 光骓者的荣耀

本题策略：
贪心
先累加出所有高速公路所需时间之和，再减去长度为k的最大子段和即可
于是我们想到维护一个前缀和序列，遍历长度为k的子串，再找出最大值
#include<bits/stdc++.h>
using namespace std;
long long a[1000005],ans,n,k;//要开longlong，谨记
int main(){
    scanf("%lld%lld",&n,&k);
    for(long long i=1;i<n;++i)
        scanf("%lld",&a[i]),a[i]+=a[i-1];//输入+维护前缀和
    for(long long i=k;i<n;++i)//遍历子串，是k到n不是k-1到n！这直接导致我一直92分
        ans=max(a[i]-a[i-k],ans);//更新最大k子串
    ans=a[n-1]-ans;//得到最小值
    printf("%lld",ans);
    return 0;
}

感觉比T2难诶，比赛一直92分。。

附比赛时的惨状：