题解 | 空间跃迁

#include <stdio.h>
#include <stdlib.h>
typedef long long ll;

int main(void) {
    int n, k;
    scanf("%d%d", &n, &k);

    if(n <= 1){
        printf("0\n");
        return 0;
    }

    ll*a = (ll*)malloc(n* sizeof(ll));
    ll*prefix = (ll*)malloc(n* sizeof(ll));
    prefix[0] = 0;
    for(int i = 0; i < n-1; i++){
        scanf("%lld", &a[i]);
        prefix[i+1] = prefix[i] + a[i];
    }
    ll sum = prefix[n-1];
    if(k== 0 || n <= k){
        printf("%lld", sum);
        free(a);
        free(prefix);
        return 0;
    }
    ll min = sum;
    for(int i = 1; i <= n-k; i++){
        ll save = prefix[i + k - 1] - prefix[i - 1];
        ll current = sum - save;
        if(current < min)
            min = current;
    }
    printf("%lld\n", min);
    
    free(a);
    free(prefix);
    return 0;
}