题解 P1714 【切蛋糕】

· · 题解

思路楼下已经说的很清楚了，这里选择了单调队列优化，又快又好写。

维护一个前缀和sum[k]的单调递增队列 ， 每次取出队首为最小值进行转移

#include<bits/stdc++.h>
#define rep(i,j,n) for(int i=j;i<=n;i++)
using namespace std;
const int N=5e5+10;
int n,m,sum[N],q[N],l=1,r,x,ans;
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,n) {
        scanf("%d",&x) , sum[i]=sum[i-1]+x;  //方便地使用前缀和数组
        while(l<=r && sum[q[r]] > sum[i]) r--;  //若不满足单调性就出队直到插入到合适的位置
        q[++r]=i;
        while(l<=r && q[l]<i-m) l++;
        ans=max(ans,sum[i]-sum[q[l]]);
    }
    //似乎这里可能存在一些小问题？比如应使用sum[i-1]进行转移? 不过大体还是一样的
    printf("%d",ans);
    return 0;
}