题解 P1714 【切蛋糕】
可以称得上是单调队列模板题了
刚学单调队列，正好写个题解
先看题目，短小的题目题意相当明确，在n个数中取连续的k（k<=m）个数，输出其中所有可能的最大值。
注意k<=m，并不要求一定为m。这就超出我朴实前缀和的能力范围了，然而对于单调队列没有什么影响
前缀和是当然要用的，输入数据顺便求出前缀和。
然后维护一个队首最大的单调队列，O（n）复杂度就轻松搞定。
因为不想单调队列开两个数组，我用struct把入队时间index和价值value同时记录
#include<cstdio>
#include<algorithm>
int cake,n,m,ans=-2333333;//蛋糕幸运值有负数，安全起见ans初始化小一点
int sum[500005];
struct node
{
int index,value;//入队时间，前缀和
}q[500005];
int main()
{
int front=1,back=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&cake);
sum[i]=sum[i-1]+cake;//计算前缀和
}
for(int i=1;i<=n;i++)
{
if(q[front].index+m<i) front++;//将已经超出范围的蛋糕出队
while(front<=back&&q[back].value>=sum[i]) back--;//将比当前蛋糕幸运值高的蛋糕出队，维护队列单调递增
q[++back].index=i;q[back].value=sum[i];//当前蛋糕一定会入队
ans=std::max(ans,q[back].value-q[front].value);
}
printf("%d\n",ans);
return 0;
}