环上选一段连续的弧(长度 1~n)使快乐值之和最大。
地铁环线有 n 个车站,站 i 的下一站是 i+1(站 n 的下一站是站 1)。小 A 从某站出发、到某站结束,至少经过一个车站,且不会重复经过同一车站。经过站 i 获得 aᵢ 点快乐值(可正可负)。求最大快乐值总和。
环形最大子段和前缀和单调队列滑动窗口最小值
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 a₁…aₙ |
| 输出 | 最大快乐值总和 |
| 数据范围 | 1 ≤ n ≤ 2 × 10⁵ |
| 快乐值 | −10⁹ ≤ aᵢ ≤ 10⁹(可为负) |
| 行程 | 环上连续弧,长度 1 ~ n |
pre[e] − pre[s];固定终点 e,只要在长度为 n 的窗口内取最小的 pre即可——这用单调队列维护先把所有长度 ≤ 4 的弧列出来(环上连续)。
| 弧长 | 候选弧(按环顺序) | 最大和 |
|---|---|---|
| 1 | [−1]、[2]、[3]、[0] | 3 |
| 2 | [−1,2]、[2,3]、[3,0]、[0,−1] | 5(2 + 3) |
| 3 | [−1,2,3]、[2,3,0]、[3,0,−1]、[0,−1,2] | 5(2+3+0) |
| 4 | [−1,2,3,0] | 4 |
最大 = 5 ✓(走车站 2 → 3)
−1:它被"绕开"了——因为我们是从车站 2 出发到车站 3,不必经过车站 1。这组数据的最优解跨过了"环的连接处",正好体现环形问题的特点。
线性数组 [−3, 4, −5, 1, 3] 的最大子段:
[4] = 4;[1,3] = 4;[4,−5,1,3] = 3
所以不跨环的最优是 4
不跨环最优 4
跨环意味着弧"绕过"了数组的首尾相接处
例如 [1, 3, −3, 4]:从站 4 出发 → 站 5 → 站 1 → 站 2
和 = 1 + 3 + (−3) + 4 = 5
这比 4 更好!
跨环可得 5
该弧长 4 ≤ n = 5 ✓
有没有长度为 5 的弧?= 整圈 = −3+4−5+1+3 = 0
所以不能更长(长度 5 本身合法但和只有 0)
最优就是 5
✅ 答案 5
最优行程:站 4 → 5 → 1 → 2,快乐值 1 + 3 − 3 + 4 = 5 ✓
前缀和 + 滑动窗口最小值,一次 O(n) 扫描
[s+1, e] 的和 = pre[e] − pre[s]。固定 e,要最大化它就最小化 pre[s],而 s 的范围是 [e−n, e−1]。这就是"滑动窗口最小值",用单调队列 O(1) 摊还维护。枚举所有弧,累加求和取最大
| 方案 | 复杂度(n = 2 × 10⁵) | 可行性 |
|---|---|---|
| 单调队列 | 约 4 × 10⁵ | ✅ 稳过 |
| 枚举起点终点 | 约 4 × 10¹⁰ | ❌ 超时 |
输入一组快乐值,程序会用环形算法求出最大值,并与暴力枚举互相验证。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; long long a[400005], pre[400005]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); a[i + n] = a[i]; // 复制一倍 } int N = 2 * n; pre[0] = 0; for (int i = 0; i < N; i++) pre[i + 1] = pre[i] + a[i]; // 单调队列:存前缀和的下标,保持 pre 递增 deque<int> dq; dq.push_back(0); long long ans = LLONG_MIN; for (int e = 1; e <= N; e++) { // 弹出超出窗口的下标(窗口是 [e - n, e - 1]) while (!dq.empty() && dq.front() < e - n) dq.pop_front(); // 用队首(窗口内最小的 pre)更新答案 ans = max(ans, pre[e] - pre[dq.front()]); // 维护单调性后把 e 入队 while (!dq.empty() && pre[dq.back()] >= pre[e]) dq.pop_back(); dq.push_back(e); } printf("%lld\n", ans); return 0; }
[e − n, e − 1]?e 是弧的右端点(在前缀和里是"第 e 个位置之后"),s 是左端点前一个位置。弧的长度 = e − s,要求 1 ≤ e − s ≤ n,所以 s ∈ [e − n, e − 1] ✓。e − s 的不等式再推。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
a[i + n] = a[i] | 复制一倍 | 把环形摊平成线性 |
pre[i + 1] = pre[i] + a[i] | 前缀和 | 让区间和能 O(1) 求出 |
while (dq.front() < e - n) pop_front() | 窗口过期 | 保证弧长 ≤ n |
pre[e] - pre[dq.front()] | 更新答案 | 队首是窗口内最小的 pre |
while (... >= pre[e]) pop_back() | 维护单调 | 保证队列里 pre 递增 |
int(和可达 2 × 10¹⁴);② 窗口边界写错(应该是 e − n,对应"弧长 ≤ n");③ 忘记"先更新答案再压入 e"的顺序(否则可能出现长度 0 的弧);④ ans 初值取 0(应为负无穷,因为答案可能是负数)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 5 | 题面样例 1(走站 2 → 3) |
5 | 5 | 题面样例 2(跨环) |
1 | 7 | 只有一个车站 |
1 | -7 | 只有一个车站且为负,必须经过它 |
3 | -1 | 全为负,取最大的单个 |
4 | 4 | 全为正,绕一整圈(经过全部 4 站一次) |
s ≥ e − n。需要存 2n 长度的数组与前缀和。
✅ 约 40 万次操作,瞬间完成。若只做一维 Kadane(不处理跨环),样例 2 会错答为 4。
// 环形最大子段和:两种经典做法 // 做法 A(推荐):复制一倍 + 前缀和 + 单调队列(本题代码) // 做法 B:分类讨论 // ans = max(不跨环的最大子段和, 总和 − 不跨环的最小子段和) // 注意:若"最小子段"就是整个数组,要特殊处理(对应"不能取空弧") // 单调队列求滑动窗口最小值(通用模板) deque<int> dq; for (int i = 0; i < N; i++) { while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front(); // 过期 while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 维护单调 dq.push_back(i); // 此时 dq.front() 就是窗口 [i-k+1, i] 内最小值的下标 } // 环形问题的通用思路 // 1. 复制一倍摊平成线性 // 2. 用"长度限制的滑动窗口"约束 // 3. 避免分类讨论"是否跨环"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 环形 → 线性 | 复制一倍 | 所有环形区间问题 |
| 滑动窗口最小值 | 单调队列 O(n) | 固定窗口长度的最值查询 |
| 前缀和 + 队列 | 区间和转成前缀差 | 子段和、区间统计类问题 |
e − n 改成 e − k。这说明单调队列框架非常灵活,窗口大小就是"约束条件"的直接映射。)