【题目来源】
洛谷：P1714 切蛋糕 - 洛谷
【题目描述】
今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 \(n\) 个相同的小块，每小块都有对应的幸运值。
小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 \(m(m\le n)\) 小块的蛋糕。
请你帮他从这 \(n\) 小块中找出连续的 \(k(1 \le k\le m)\) 块蛋糕，使得其上的总幸运值最大。
形式化地，在数列 \(\{p_n\}\) 中，找出一个子段 \([l,r](r-l+1\le m)\)，最大化 \(\sum\limits_{i=l}^rp_i\)。
【输入】
第一行两个整数 \(n,m\)。分别代表共有 \(n\) 小块蛋糕，小 Z 最多只能吃 \(m\) 小块。
第二行 \(n\) 个整数，第 \(i\) 个整数 \(p_i\) 代表第 \(i\) 小块蛋糕的幸运值。
【输出】
仅一行一个整数，即小 Z 能够得到的最大幸运值。
【输入样例】
5 2
1 2 3 4 5
【输出样例】
9
【算法标签】
《洛谷 P1714 切蛋糕》 #单调队列# #前缀和# #队列# ST表
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long // 将int重新定义为long long类型
const int N = 500005; // 定义常量N，最大数组大小
int n, m, a[N], sa[N], ans = -1e9; // n: 数组长度, m: 最大子数组长度, a: 原始数组, sa: 前缀和数组, ans: 结果struct Node
{int s, idx; // s: 前缀和值, idx: 索引位置
};
deque<Node> dq; // 双端队列，用于维护滑动窗口最小值signed main() // 因为使用了#define int long long, 所以用signed main
{cin >> n >> m; // 输入数组长度和最大子数组长度for (int i = 1; i <= n; i++){cin >> a[i]; // 输入数组元素sa[i] = sa[i - 1] + a[i]; // 计算前缀和}for (int i = 1; i <= n; i++){// 维护队列：删除超出窗口范围的元素// 窗口大小为m，只考虑i-m到i-1的前缀和while (dq.size()){if (dq.front().idx < i - m) // 如果队首元素索引小于i-m，超出窗口范围dq.pop_front(); // 删除队首元素else break; // 否则停止}// 维护队列：保持队列单调递增// 如果队尾元素的前缀和大于等于当前前缀和，则删除队尾元素// 因为对于后面的i来说，当前元素更优（前缀和更小，索引更靠后）while (dq.size()){if (dq.back().s >= sa[i - 1]) // 如果队尾元素的前缀和大于等于当前前缀和dq.pop_back(); // 删除队尾元素else break; // 否则停止}// 将当前元素的前缀和加入队列dq.push_back({sa[i - 1], i - 1});// 更新答案：当前前缀和减去队列最小值// 即sa[i] - sa[j] 表示子数组a[j+1...i]的和ans = max(ans, sa[i] - dq.front().s);}cout << ans << endl; // 输出最大子数组和return 0;
}
【运行结果】
5 2
1 2 3 4 5
9