Educational Codeforces Round 69 D Yet Another Subarray Problem

D Yet Another Subarray Problem

思路

• 求一段区间满足这个条件的最大值，这个等式的一个特点是，区间长度增加m，才减掉一个k，并且题目中m的数据范围是很小的。
• 可以考虑枚举起点，但是我们枚举起点之后，后面的更新不知道怎么样快速更新求解。
• 枚举小于m的数，0~m-1，也可以看成枚举前m-1个位置。对于起点之后，每增加m个位置，sum和需要减掉k。维护一个最小值minn（初始值设为0，因为最大为不取的情况，就是0）。在后续枚举的过程中，每当需要减掉k之前，更新一下minn，表示取前面几段的最小值。在每次枚举时，更新答案res=max(res,sum-minn),表示当前的前缀和-前面某段的前缀和最小值来更新答案。
• 为什么不能在每个点处更新minn呢？因为-k操作是每隔m才出现的，同一段内不能多次-k，如果每个点都更新minn，那么同一段区间内，sum-minn就消除了需要减k的值。例如样例2 ，-4， 15。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[300005];
int main()
{
    int n, m, k;
    ll res = 0;
    scanf("%d%d%d", &n,&m,&k);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);

    for(int i=0;i<m;i++){
        ll minn=0;//最大为0
        ll sum=0;
        for(int j=i;j<n;j++){
            if(j%m==i){
                minn=min(sum,minn);
                sum-=k;
            }
            sum+=a[j];
            res=max(res,sum-minn);
        }

    }
    printf("%lld\n", res);
}