题解：AT_past20_e リンゴ集め

yanwencan · 2026-07-20 20:24:40 · 题解

首先，这题数据量 10^6 肯定不能暴力。

那我们这时就需要预处理来将时间复杂度降至 O (n) 也就是前缀和！

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,w,a[1000010];
int maxx=INT_MIN;//INT_MIN顾名思义
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[i]=a[i-1]+x;//可以直接覆盖原数
    }
    for(int i=w;i<=n;i++){
        maxx=max(maxx,a[i]-a[i-w]);//比大小
    }
    cout<<maxx;
    return 0;
}