题解 P1714 【切蛋糕】
Apro1066
·
·
题解
这里用的C++ STL实现：$deque$，即双向队列。
```cpp
#include <stdio.h>
#include <iostream>
#include <deque>
#define linf -2e9-7
using namespace std;
int n,m,s,sum[500001];
struct node
{
int v,position;//序列的值，位置
}a[500001];
deque<node> dq;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
register int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i].v;
sum[i]=sum[i-1]+a[i].v;//前缀和
a[i].position=i;//位置记录
}
for(i=1;i<=n;i++)
{
while(!dq.empty() && dq.front().position<i-m)//不在区间的要出队
dq.pop_front();
s=max(s,sum[i]-sum[dq.front().position]);//取最大值
while(!dq.empty() && sum[i]<=sum[dq.back().position])//维护单调递增的序列
dq.pop_back();
dq.push_back(a[i]);//元素入队
}
cout<<s<<endl;
return 0;
}
```