1 solutions

  • 0
    @ 2025-6-9 22:05:13

    需要我们维护的区间长度固定,那么我们可以用一种简单的方法O(n)处理。

    例如样例数据中,我们只需要把前3个数值计为sum,在m+1...n中扫描,每次减去区间外的数值,加上新进入区间的数值,再更新答案就可以了。

    代码还是简短一点比较好看哦~

    #include <bits/stdc++.h>
    using namespace std;
    int n,m;
    int hrt[3010];
    int ans;
    int sum;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) {
            scanf("%d",&hrt[i]);
            if(i<=m){
                sum+=hrt[i];
                ans=sum;
            }
            else
                ans=min(ans,sum+=hrt[i]-hrt[i-m]);
        }
        cout<<ans;
        return 0;
    }
    
    • 1

    Information

    ID
    116
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    2
    Accepted
    2
    Uploaded By