文章总数40祭+P1714 切蛋糕 题解
P1714 切蛋糕 题解
算法分析：单调队列
最近一直在刷单调队列的题，这道题可以用来练练手
step1:把比自己大的出队列
stdp2:将当前前缀入队列
step3:将超出距离的出队列
stdp4:更新答案
std:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define frep(i,x,y) for(int i=x;i>=y;i--)
#define INF 2147483647
#define ll long long
const int N=500005;
int n,m;
ll a[N];
ll s[N];
int q[N];
int h=1,t=0;
ll ans=-INF;
int main()
{
s[0]=0;
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%lld",&a[i]);
rep(i,1,n) s[i]=s[i-1]+a[i];//计算前缀
rep(i,1,n)
{
while(h<=t&&s[q[t]]>=s[i]) t--;//1出
q[++t]=i;//2入
while(q[h]<i-m) h++;//3出
ans=max(ans,s[i]-s[q[h]]);//4新
}
printf("%d\n",ans);//愉快输出
return 0;
}