题解 P1614 【爱与愁的心痛】

Dog_Two · 2018-01-05 19:50:17 · 题解

需要我们维护的区间长度固定，那么我们可以用一种简单的方法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]),ans=i<=m?sum+=hrt[i]:min(ans,sum+=hrt[i]-hrt[i-m]);
    cout<<ans;
    return 0;
}