切蛋糕

题目 切蛋糕

image-d2fa7194

思路分析

有n块蛋糕 他要吃连续的m块 要这m块得到的权值最大

其实就转变成了 最大子序和 问题

本来还在想本身就是单调的 幸运值嘛 构造前缀和肯定都大于0

但是一看幸运值还有负……

那就和那题一模一样了

有个问题是 结果如果小于0 要强制输出0 题目没说这个事情 但是检验要求

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=500010;

int s[N],q[N],hh=0,tt=0;

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        int x;cin>>x;

        s[i]=s[i-1]+x;

    }

    int res=INT_MIN;

    for(int i=1;i<=n;i++)

    {

        if(hh<=tt && i-q[hh]>m)

            hh++;

        res=max(res,s[i]-s[q[hh]]);

        while(hh<=tt && s[i]<=s[q[tt]])

            tt--;

        q[++tt]=i;

    }

    cout<<((res<0)?0:res)<<endl;

    return 0;

}

同类题型

视频讲解

⬅️ 单调队列 🏠 00-刷题理模型 ➡️ 单调队列