---
title: "切蛋糕"
created: 2025-11-28
tags:
  - 算法
---

# 切蛋糕

## 题目 [切蛋糕](https://www.acwing.com/problem/content/description/654/)

![[image-d2fa7194.png]]

## 思路分析

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

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

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

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

那就和那题一模一样了

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

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列|单调队列]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调队列/单调队列|单调队列]]