切蛋糕

GitHub返回列表

OJ: luogu

题目 ID: P1714

标签: 前缀和单调队列

日期: 2025-12-26 19:34

目录

  1. 1. 题目简述
  2. 2. 思路分析
    1. 朴素前缀和（ - 超时）
    2. 单调队列优化（ - 正解）
  3. 3. 样例推演
  4. 4. AC 代码
  5. 5. 总结

题解：最大子序和 (限定长度)

1. 题目简述

给定一个长度为 nn 的序列，要求找到一个长度不超过 mm 的连续子序列（子段），使得该子序列的元素和最大。

形式化： 在数列 pp 中，找出一个子段 [l,r][l,r]，满足 r−l+1≤mr-l+1 \le m，最大化 ∑i=lrpi\sum_{i=l}^r p_i。

数据范围： n≤5×105n \le 5 \times 10^5，元素绝对值 ≤500\le 500。

2. 思路分析

朴素前缀和（O(n2)O(n^2) - 超时）

首先，对于区间求和问题，我们第一时间想到前缀和。 设 S[i]S[i] 表示前 ii 个数的和，即 S[i]=∑k=1ipkS[i] = \sum_{k=1}^i p_k，S[0]=0S[0]=0。 那么子段 [l,r][l, r] 的和可以表示为：Sum(l,r)=S[r]−S[l−1]Sum(l, r) = S[r] - S[l-1]。

题目要求找出 max(S[r]−S[l−1])max(S[r] - S[l-1])，其中 1≤r−l+1≤m1 \le r - l + 1 \le m。 令 j=l−1j = l-1，也就是在枚举右端点 ii (即原题的 rr) 时，我们需要找到一个左端点 jj，满足：

  1. i−m≤j<ii - m \le j < i （区间长度限制）
  2. 使得 S[i]−S[j]S[i] - S[j] 最大。

对于固定的 ii，要让 S[i]−S[j]S[i] - S[j] 最大，就是要让 S[j]S[j] 最小。

如果暴力枚举 ii 和 jj，时间复杂度是 O(n×m)O(n \times m)，在 n=5×105n=5 \times 10^5 时会超时。

单调队列优化（O(n)O(n) - 正解）

我们发现，当 ii 向右移动一位变成 i+1i+1 时，可选的 jj 的范围也整体向右移动一位。这是一个典型的滑动窗口模型。

我们需要在窗口 [i−m,i−1][i-m, i-1] 中找到一个 jj，使得 S[j]S[j] 最小。 这正是单调队列的拿手好戏：维护一个单调递增的队列（队首对应的 SS 值最小）。

具体步骤：

  1. 预处理：计算前缀和数组 SS。
  2. 初始化：单调队列中先放入下标 00（因为 S[0]=0S[0]=0 是一个合法的减数，对应从第1个数开始选的情况）。
  3. 遍历：ii 从 11 到 nn：
    • 去尾（维护单调性）：如果当前 S[i]S[i] 比队尾元素对应的 SS 值还小，说明当前的 S[i]S[i] 更优且更靠后，队尾元素淘汰。弹出队尾，直到满足单调性或队列空。
    • 入队：将当前下标 ii 入队（注意：这里 ii 入队是作为未来 i′>ii' > i 时的减数 S[j]S[j] 存在的）。
    • 删头（维护时效性）：检查队头元素 idxidx。我们当前计算答案时，右端点是 ii，那么合法的左端点 jj 必须满足 j≥i−mj \ge i-m。如果 q.front()<i−mq.front() < i - m，说明这个 jj 离得太远了，超出了长度 mm 的限制，弹出队头。
    • 更新答案：此时队头元素就是当前窗口内最小的 S[j]S[j]。最大子段和 =S[i]−S[q.front()]= S[i] - S[q.front()]。

注意点： 这里操作顺序略有讲究。对于当前的 ii，它既是计算答案时的右端点，也是未来作为左端点的候选人。 由于题目要求子段长度至少为1，即 i≠ji \neq j，所以我们在计算答案时，不能使用刚放入队列的 ii 作为 jj。因此通常先检查队头过期、更新答案，最后再把 ii 放入队列（或者入队前先更新答案）。

3. 样例推演

输入：n=5, m=2，数组 1 2 3 4 5 前缀和 SS: 0, 1, 3, 6, 10, 15

i 当前 S[i] 队列状态 (存下标) 队头是否过期? (j<i−mj < i-m) 计算答案 S[i]−S[q.front()]S[i] - S[q.front()] 维护单调性并入队
init S[0]=0S[0]=0 {0} - - -
1 S[1]=1S[1]=1 {0} 否 (0≥1−20 \ge 1-2) 1−0=11 - 0 = 1 S[1]>S[0]S[1]>S[0], 直接入队 {0, 1}
2 S[2]=3S[2]=3 {0, 1} 否 (0≥2−20 \ge 2-2) 3−0=33 - 0 = 3 S[2]>S[1]S[2]>S[1], 直接入队 {0, 1, 2}
3 S[3]=6S[3]=6 {0, 1, 2} 是 (0<3−20 < 3-2), 弹出0 -> {1, 2} 6−1=56 - 1 = 5 S[3]>S[2]S[3]>S[2], 入队 {1, 2, 3}
4 S[4]=10S[4]=10 {1, 2, 3} 是 (1<4−21 < 4-2), 弹出1 -> {2, 3} 10−3=710 - 3 = 7 入队 {2, 3, 4}
5 S[5]=15S[5]=15 {2, 3, 4} 是 (2<5−22 < 5-2), 弹出2 -> {3, 4} 15−6=915 - 6 = 9 入队 {3, 4, 5}

最终答案：9。

4. AC 代码

cpp
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

// 即使题目说由int范围，但涉及累加，开long long是个好习惯
using ll = long long;

const int MAXN = 500005;
ll s[MAXN]; // 前缀和数组

int main() {
    // I/O 加速
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }

    // 单调队列存放下标，维护的是 S[j] 的最小值（单调递增队列）
    deque<int> q;
    q.push_back(0); // 初始化，放入S[0]

    // 初始化答案为一个极小值
    ll max_ans = -1e18; 

    for (int i = 1; i <= n; ++i) {
        // 1. 移除过期元素 (队头下标 j 必须满足 i - j <= m，即 j >= i - m)
        // 如果 q.front() < i - m，说明该左端点距离 i 超过了 m，不合法
        while (!q.empty() && q.front() < i - m) {
            q.pop_front();
        }

        // 2. 更新答案
        // 当前合法的最小前缀和就是 s[q.front()]
        // 以 i 为结尾的最大子段和 = s[i] - min(s[j])
        if (!q.empty()) {
            max_ans = max(max_ans, s[i] - s[q.front()]);
        }

        // 3. 维护单调性并入队 (准备作为未来的左端点 j)
        // 我们需要队列保持单调递增 (因为我们要找最小的 S[j] 来减)
        // 如果当前的 s[i] 比队尾的 s[back] 还小，那队尾就没用了
        while (!q.empty() && s[q.back()] >= s[i]) {
            q.pop_back();
        }
        q.push_back(i);
    }

    cout << max_ans << endl;

    return 0;
}

5. 总结

  • 转化问题：将“子段和最大”转化为“前缀和差值最大” (S[i]−S[j]S[i] - S[j])。
  • 固定一端：枚举右端点 ii，问题变为在合法范围内找最小的 S[j]S[j]。
  • 单调队列：维护一个值单调递增的队列，存储下标。
    • 取值：取队头 (最小的减数)。
    • 入队：保持单调递增 (若当前值更小，则弹出队尾)。
    • 出队：判断下标距离是否超过 mm。