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

opened · 2019-11-10 11:58:34 · 题解

文件快读、快输自提

首先想 O(n^2) 暴力，枚举在每个点使用传送器，再用前缀和优化一下，复杂度 O(n)

注意开 long\ long

#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
typedef long long ll;
ll n,k,s[1000100];
inline char getcha(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read(){
    ll res=0;char ch=getcha();bool XX=false;
    for(;!isdigit(ch);ch=getcha()) (ch=='-') && (XX=true);
    for(;isdigit(ch);ch=getcha()) res=(res<<3)+(res<<1)+(ch^48);
    return XX?-res:res;
}
void write(ll x){
    static int sta[35];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top) cout<<sta[--top];
}
int main(){
    ios::sync_with_stdio(0);
    n=read(),k=read();
    for(register int i=1;i<n;i++){
        ll x=read();
        s[i]=s[i-1]+x;
    }
    if(k==0){
        write(s[n-1]);
        return 0;
    }
    ll ans=0;
    for(register int i=1;i+k<=n;i++)
        if(ans<s[i+k-1]-s[i-1]) ans=s[i+k-1]-s[i-1];
    ll a=s[n-1]-ans;
    write(a);
    return 0;
}