1 solutions
-
0
需要我们维护的区间长度固定,那么我们可以用一种简单的方法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