P3351 成绩报告最大值问题：单调队列优化O(n)解法

好的，我们先仔细分析一下这个题目，然后给出 **高效的 C++ 解法**。 --- ## 🧠 题目理解与转化 我们有一个长度为 `n` 的整数数组，表示考试成绩。汇报顺序可以有两种： 1. 原始顺序：`1, 2, 3, ..., n` 2. **倒叙策略**：从某个 `k` 开始，按 `k, k+1, ..., n, 1, 2, ..., k-1` 的顺序汇报。 妈妈的心情初始为 0，每汇报一个成绩，心情累加该成绩。 我们关心的是 **整个汇报过程中妈妈心情的最大值**。 目标： 在所有可能的 `k`（从 1 到 n）中，找出能使最大心情值最大的那个 `k`，如果有多个，输出最小的 `k`，以及该最大心情值。 --- ### 🔍 关键观察 - 如果直接枚举每个 `k` 并模拟整个过程，复杂度是 O(n²)，对于 n ≤ 10⁶ 会超时。 - 我们需要 **O(n) 或 O(n log n)** 的算法。 - 这里可以用 **前缀和 + 循环数组最大子段和** 的技巧。 --- ### 📐 数学化 定义原始数组为 `a[1..n]`，前缀和 `pref[i] = a[1] + a[2] + ... + a[i]`，`pref[0] = 0`。 对于起始位置 `k`，汇报顺序为： ``` a[k], a[k+1], ..., a[n], a[1], a[2], ..., a[k-1] ``` 心情值变化相当于： - 先从 0 开始，依次加上 `a[k], a[k+1], ..., a[n]` 到这里的累加和 = `pref[n] - pref[k-1]` - 然后加上 `a[1], a[2], ..., a[k-1]` 累加和继续增加，直到最终总和 `pref[n]`。 但我们要的是过程中的 **最大值**，不是最终值。 --- ### 💡 关键思路 对于每个 `k`，整个汇报过程相当于对数组做了循环移位，然后求这个新数组的**前缀和最大值**。 我们可以利用**将数组复制一遍**的技巧（长度 2n），然后对于每个 `k`，考虑区间 `[k, k+n-1]` 的前缀和最大值。 **但是**，直接做每个区间的最大值还是 O(n²)。 --- ### ⚡ 更优方法：滑动窗口 + 前缀和最小前缀 我们对于每个位置 `i`（原始数组位置）， 定义从 `k` 开始到某个位置 `j` 的累加和为： ``` sum(k, j) = pref[j] - pref[k-1] （当 j >= k 时） ``` 当越过 n 时，就使用循环数组的转化： 我们可以将数组复制为 `b[1..2n]`，其中： ``` b[i] = a[i] (1 ≤ i ≤ n) b[n+i] = a[i] (1 ≤ i ≤ n) ``` 然后，对于每个起始位置 `k` (1 ≤ k ≤ n)，我们看区间 `[k, k+n-1]`： - 心情值从0开始 - 心情在位置 `j` 的值 = `pref_b[j] - pref_b[k-1]` 其中 `pref_b` 是 b 的前缀和，`pref_b[0] = 0`。 我们需要这个区间内的 `(pref_b[j] - pref_b[k-1])` 的最大值。 所以对于每个 `k`，最大值 = `(max_{j in [k, k+n-1]} pref_b[j]) - pref_b[k-1]` 于是问题转化为： > 对于每个长度为 n 的滑动窗口，求窗口内前缀和的最大值。 这个可以用 **单调队列（双端队列）** 在 O(n) 时间内完成。 --- ### 🧩 算法步骤 1. 读入 n 和数组 a。 2. 构造数组 b 长度 2n：`b[i] = a[i]`，`b[n+i] = a[i]`。 3. 计算 b 的前缀和数组 `pref_b`，长度 2n+1，`pref_b[0]=0`。 4. 用单调递减队列维护窗口 `[k, k+n-1]` 内的 `pref_b` 最大值索引。 5. 对于每个 k (1..n)： - 窗口右端是 `k+n-1`，左端是 `k` - 从队首取出最大值的索引 `max_idx` - 当前 `max_happiness = pref_b[max_idx] - pref_b[k-1]` - 如果大于全局最大，更新；等于且 k 更小也更新。 6. 输出 k 和 max_happiness。 --- ### ✅ C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // 构造长度为2n的数组 vector<long long> b(2 * n); for (int i = 0; i < n; ++i) { b[i] = a[i]; b[i + n] = a[i]; } // 前缀和 vector<long long> pref(2 * n + 1, 0); for (int i = 0; i < 2 * n; ++i) { pref[i + 1] = pref[i] + b[i]; } // 单调队列，存储索引 deque<int> dq; long long max_happiness = LLONG_MIN; int best_k = 1; // 滑窗长度为n for (int i = 1; i <= 2 * n; ++i) { // 移除队尾比当前pref小的（保持递减） while (!dq.empty() && pref[dq.back()] <= pref[i]) { dq.pop_back(); } dq.push_back(i); // 移除不在窗口 [k, k+n-1] 内的索引 // 窗口左端为 i-n+1 int window_start = i - n + 1; while (!dq.empty() && dq.front() < window_start) { dq.pop_front(); } // 当窗口完整时 (i >= n) if (i >= n) { int k = i - n + 1; // 对应原始数组的起始位置（1-based） long long current_max = pref[dq.front()] - pref[k - 1]; if (current_max > max_happiness) { max_happiness = current_max; best_k = k; } else if (current_max == max_happiness && k < best_k) { best_k = k; } } } // 注意：k 在代码中是1-based，对应原始顺序的编号 cout << best_k << " " << max_happiness << endl; return 0; } ``` --- ### 📌 复杂度分析 - **时间复杂度**：O(n) 我们遍历了 2n 个元素，每个元素入队出队最多一次。 - **空间复杂度**：O(n) 存储 a、b 和 pref 需要 O(n) 空间，队列也是 O(n)。 --- ### ⚠️ 注意事项 - 数据范围 n ≤ 10⁶，使用 `long long` 防止前缀和溢出。 - 成绩范围较小，但累加和可能很大，所以要用 `long long`。 - 单调队列一定要维护 **递减** 顺序，保证队首是窗口最大值。 --- ### 🧪 样例验证 样例： ``` 4 -3 5 1 2 ``` 输出： ``` 2 8 ``` 解释： 从第2个开始，顺序是 `5 1 2 -3`，心情变化： ``` 0 -> 5 -> 6 -> 8 -> 5 ``` 最大值是 8，在报告第3个成绩时达到。 --- ### 📘 开发建议 1. **善用 `ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)`** 提高输入速度。 2. 对于大规模数据，优先考虑 O(n) 或 O(n log n) 算法。 3. 滑动窗口 + 单调队列是处理“固定长度区间最值”的经典套路，建议熟练掌握。 4. 边界条件要仔细：1-based 与 0-based 索引转换容易出错。 --- ######[AI写代码神器 | 1978点数解答 | 2026-07-05 10:24:58]