题解 P1714 【切蛋糕】

· · 个人记录

挺好的一道题，但对我这样的蒟蒻来说还是难度不小的。。。

一开始并没有读清题，后来才发现吃的块数自己定

那么很显然，我们不能用一般的前缀和来做这道题

于是就掏出了最近用的很多的单调队列

我们只需要确保从 i（循环变量） 到 单调队列的队首元素 这段区间中的幸运值最大即可

单调队列自然不多说，一般的维护即可

我本人因为数组模拟队列用不习惯，还是STL吧

注：这边代码中的单调队列记录的是序号，如果不习惯的话开两个队列一个存值一个存序号也是极好的

具体见代码

#include<bits/stdc++.h>//万能 
using namespace std;
deque <int> q;//单调队列 
int ans=-2147400000,n,m,a,f[500005];//ans初值不要忘记设 
int Max(int x,int y)
{
    return x > y ? x : y;
}//手写一个速度比较快 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        f[i]=f[i-1]+a;//建立前缀和 
    }
    for(int i=1;i<=n;i++)
    {
        while(!q.empty() && f[q.back()]>f[i]) q.pop_back();
        //维护单调队列，确保队首最大 
        q.push_back(i);//将当前位置推入队列 
        while(q.front()<i-m) q.pop_front();//越界的弹出 
        ans=Max(ans,f[i]-f[q.front()]);//记录答案 
    }
    printf("%d",ans);//输出，结束 
    return 0;
}