P76027 最短栅栏 — 题解

专题： 前缀和
适用题目： 新生 OJ 本地题包中的 P76027，不要直接用于外站同名题。

解题思路

先求前 k 个木板的总高度，然后每次右移一格：加新木板高度，减旧木板高度。

复杂度

时间 $O(n)$，空间 $O(n)$。

易错点

相同最小值时保留最左边起点，更新应使用严格小于。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n,k;scanf("%d%d",&n,&k);long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    long long curr=0;
    for(int i=0;i<k;i++)curr+=a[i];
    long long best=curr;int pos=1;
    for(int i=k;i<n;i++){
        curr+=a[i]-a[i-k];
        if(curr<best){best=curr;pos=i-k+2;}
    }
    printf("%d\n",pos);free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<ll>a(n);
    for(auto &x:a)cin>>x;
    ll sum=accumulate(a.begin(),a.begin()+k,0LL),best=sum;
    int index=1;
    for(int i=k;i<n;i++){
        sum+=a[i]-a[i-k];
        if(sum<best){
            best=sum;
            index=i-k+2;
        }
    }
    cout<<index<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。