Educational Codeforces Round 69 D Yet Another Subarray Problem

时间:2022-12-22 10:51:39

D Yet Another Subarray Problem

Educational Codeforces Round 69 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);
}