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

　　　吾皇 · 2019-11-10 01:00:58 · 题解

最朴素的暴力做法 由于良心出题人数据范围极小，考虑枚举在2到n-k+1处传送所需的时间 这里使用前缀和维护

至于为什么是到n-k+1 ，因为a_i>=0 所以sum_{i+1}>=sum_i

#include<bits/stdc++.h>
using namespace std;
int n,k;
#define ll long long
ll a[1000001],sum[1000001],ans=1000000000000000000;//这里设一个很大的数 
static char buf[100000],*pa=buf,*pb=buf;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
inline ll read(){
    register ll x(0);register char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x;
}//非常好用的读入优化
int main(){
    n=read(),k=read();
    for(register int i=2;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];//前缀和处理
    for(register int i=2;i<n-k;i++) ans=min(ans,sum[i-1]+sum[n]-sum[i+k-1]);//求最小值
    printf("%lld",ans);
}