P1714 切蛋糕

发现以前的题解写的有点问题，现在来改一下。

题目的意思大概就是取连续的k（k<=m）个数，求其中所有可能的最大值。

大家很快就能想到暴力做法三重循环，稍加思考就可以想到第三重循环的累加过程可以用前缀和预处理出来。

既然已经想到了前缀和，就可以继续思考。对于每一个i，要求max（sum[i]-sum[j]）（i-m<=j<=i-1）。这题没有说清楚到底可不可以一块都不取，这就决定了j<=i-1还是j<=i。到这里时间复杂度为O（n^2）。

我们可以发现，对于每一个i来讲，sum[i]是固定的，于是就转化成了sum[i]-min（sum[j]）（i-m<=j<=i-1）。这就转化为了求区间最小值问题。下面有多种不同的做法，单调队列、st表、树状数组、线段树等都可以。单调队列是O（n），其它基本上是O（nlogn）。

单调队列就是维护一个单调递增或递减的队列，使得及时排除无用的决策，并且快速找到最优决策。每个元素只会入队一次出队一次，所以时间复杂度为O（n）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,INF=1e9;
int sum[N],q[N];
int main()
{
?? ?int n,m;scanf("%d%d",&n,&m);
?? ?for (register int i=1;i<=n;++i)
?? ?{
?? ??? ?int x;scanf("%d",&x);
?? ??? ?sum[i]=sum[i-1]+x;//求前缀和?
?? ?}
?? ?int head=1,tail=1,ans=-INF;q[1]=0;//注意有可能有负数?
?? ?for (register int i=1;i<=n;++i)
?? ?{
?? ??? ?while (head<=tail&&q[head]<i-m) head++;//已经不在范围内要出队?
?? ??? ?ans=max(ans,sum[i]-sum[q[head]]);
?? ??? ?while (head<=tail&&sum[i]<=sum[q[tail]]) tail--;//维护单调递增的队列?
?? ??? ?q[++tail]=i;
?? ?}
?? ?printf("%d\n",ans);
?? ?return 0;
}