C++ 稀疏表高效求解“发射站最高接收能量”问题

好的，这是一个典型的**区间内最高点接收能量**的问题，我们可以用数据结构或巧妙扫描来高效求解。 让我先帮你梳理清楚题意，然后给出高效的C++解法。 --- ## 📋 题目理解 我们有N个发射站，排成一行，每个站i有高度H[i]和能量V[i]。 每个站发射的能量**只能**被距离它不超过k的范围内**高度最高**的那个站接收（可能包括自己）。 也就是说，对于每个站i，我们要看区间`[i-k, i+k]`内H值最大的那个站j，然后把V[i]累加到站j的接收能量上。 最后找出所有站中接收能量的最大值。 --- ## ⚠️ 暴力做法不可行 最朴素的做法是：对每个i，遍历区间找最高点。 但数据范围 N ≤ 10⁶，暴力 O(N·k) 显然超时。 我们需要**线性或接近线性**的算法。 --- ## 💡 高效解法思路 ### ✅ 核心观察 每个站i的贡献（V[i]）最终只会落到它左右k范围内最高的那个站上。 关键点在于： - 如果站在某个区间内是“局部最高”，它就会“吸走”这个区间内所有发射的能量。 - 我们可以用**单调栈**风格来分配能量，而不是每个站单独找。 具体思路： 1. 从左到右扫描，维护一个**递减的单调栈**（按高度），同时记录每个站能接收左边k范围内的能量。 2. 从右到左扫描，再分配右边k范围内的能量。 3. 最终取每个站接收能量的最大值。 --- ### ✅ 算法步骤（伪代码） ``` 输入 N, k 读入 H[1..N], V[1..N] 初始化 receive[1..N] = 0 // 第一遍：从左到右，处理左边的能量传递 维护一个双端队列（或单调栈），里面存（高度, 位置, 当前接收能量累计） 对于 i = 1 to N: // 移除队列中位置 < i - k 的元素（超出左范围） // 队列按高度递减，队首是当前窗口内最高 // 把 V[i] 累加到队首那个站 // 将当前站加入队列，维持递减 // 第二遍：从右到左，处理右边的能量传递 类似，但方向相反，窗口范围 [i, i+k] 最后输出 max(receive[1..N]) ``` --- ### ✅ 使用双端队列（deque）维护滑动窗口最大值 这是一个经典技巧： - 队列中存**索引**，按照高度递减排列。 - 每次新元素入队前，把尾部比它低的全部弹出。 - 头部如果超出窗口范围（索引 < i - k）也弹出。 这样每次队首就是当前窗口内最高的站。 --- ## 💻 C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10; int H[MAXN], V[MAXN]; long long receive[MAXN]; // 可能超过int范围，用long long int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, k; cin >> N >> k; for (int i = 1; i <= N; i++) { cin >> H[i] >> V[i]; } // 从左到右：接收左边k范围内的能量（不包括自己右边） deque<int> dq; // 存索引，按高度递减 for (int i = 1; i <= N; i++) { // 移除超出左边窗口范围（< i - k）的元素 while (!dq.empty() && dq.front() < i - k) { dq.pop_front(); } // 如果栈不为空，当前窗口最高就是队首 if (!dq.empty()) { int top_idx = dq.front(); receive[top_idx] += V[i]; } // 把当前站加入队列，维持单调递减 while (!dq.empty() && H[dq.back()] <= H[i]) { dq.pop_back(); } dq.push_back(i); } // 从右到左：接收右边k范围内的能量（不包括自己左边） dq.clear(); for (int i = N; i >= 1; i--) { while (!dq.empty() && dq.front() > i + k) { dq.pop_front(); } if (!dq.empty()) { int top_idx = dq.front(); receive[top_idx] += V[i]; } while (!dq.empty() && H[dq.back()] <= H[i]) { dq.pop_back(); } dq.push_back(i); } // 注意：每个站自身发射的能量也算给自己，但是上面两遍不会重复加， // 因为上面逻辑是把能量加到“区间最高”上，如果这个站本身就是最高，会加到自己。 // 因为第一遍自己还没入队，所以左边没加自己；第二遍自己也没入队，所以右边没加自己。 // 但我们上面的逻辑里，每个i的V[i]是加到“当前窗口最高”上，如果最高就是自己呢？ // 第一遍时，我们是在入队当前元素之前，把V[i]加到队首（即前一个区间最高）， // 所以自己的V不会加给自己。 // 同理第二遍也是。 // 我们需要单独把V[i]加给每个站自己。 // 或者换个方式：在入队后，再处理能量。 // 下面采用修正方式：显式加自己。 for (int i = 1; i <= N; i++) { receive[i] += V[i]; } long long ans = 0; for (int i = 1; i <= N; i++) { if (receive[i] > ans) ans = receive[i]; } cout << ans << "\n"; return 0; } ``` --- ## 📌 关键点解释 | 步骤 | 说明 | |------|------| | 从左到右扫描 | 把当前发射站的能量加到它左边窗口内的最高站 | | 从右到左扫描 | 把当前发射站的能量加到它右边窗口内的最高站 | | 单调队列 | 保持队首始终是当前窗口内最高，删除过期元素和较低元素 | | 最后加自己 | 自己被“区间最高”能接收自己的能量（如果自己就是最高） | --- ## 🧪 样例验证 样例： ``` 3 1 4 2 3 5 6 10 ``` - 站1 (H=4, V=2)：左右1范围内最高是站3(H=6)，所以V1给站3 → receive[3] += 2 - 站2 (H=3, V=5)：左右1范围内最高是站3 → receive[3] += 5 - 站3 (H=6, V=10)：左右1范围内最高是自己 → receive[3] += 10 最终 receive[3] = 2+5+10 = 17? 等一下，样例输出是15，说明我理解有误？ 让我们重新核对题目： > 第i个发射站发射的能量，会被[i-k, i+k]中最高的发射站接收，可以是自身。 但是**注意**：区间[i-k, i+k]是包含i本身的。 站1区间[0,2]（实际1,2），最高是站1？不对，站1 H=4，站2 H=3，站3 H=6，区间[1,2]内最高是站1（H=4>3）。 站2区间[1,3]内最高是站3（H=6）。 站3区间[2,4]内最高是站3（H=6）。 所以： - 站1能量给站1 - 站2能量给站3 - 站3能量给站3 结果：receive[1]=2, receive[3]=5+10=15。 哦，所以我的算法里有个问题：在从左到右扫描时，还没加入自己，所以会**丢失自己接收自己能量的情况**。 修正方案： **对于每个i**，在其发射时，它应当被**当前区间最高站**接收，而**在把当前站加入队列之前**，要根据当前站的高度判断它是否比区间最高更大？ 不对，它应该基于**包含它自己在内**的区间最高站。 正确做法是： **对于每个i**： 1. 先把当前站加入队列（这样它就能参与成为最高）。 2. 然后队首就是区间[i-k, i+k]内的最高站（包括自己）。 3. 把V[i]加到队首。 但是这样队列可能包含未来位置？不，因为我们按顺序处理，我们只能知道当前及左边的信息。 **更严谨的做法**： - 先从左到右：对于每个i，把V[i]加到“左边窗口”最高站上（不包含自己右边）。 - 从右到左：对于每个i，把V[i]加到“右边窗口”最高站上（不包含自己左边）。 - 这样每个站除了自己，都会从左右各来一次。 - 最后自己加自己一次，总共3个来源。 再次验证： - 站1：左窗口[1,2]最高站1 → receive[1]+=2；右窗口[1,2]最高站1 → receive[1]+=2；自己加自己 → +2 这样站1得到6，显然是错的，因为区间[1,2]只有站1和站2，最高是站1没错，但站1的能量应该只给一次。 所以问题在于“左右窗口”划分时重复算了同一范围。 **根本原因**： 我们的左右两遍扫描，实际上把每个i的区间拆成左半和右半，但中间重叠部分（即站i本身）会导致重复或遗漏。 **更稳妥的方案**： 对于每个i，直接找区间[i-k, i+k]内的最高站，用类似“滑动窗口最大值”的在线做法。 **滑动窗口最大值 + 能量分配** 我们可以维护一个大小为2k+1的滑动窗口，每次滑动时，窗口内最高站不变或变化。 但我们不能直接对每个i分配能量，因为元素会动态进出窗口。 --- ## ✅ 正确解法（更清晰） 用 **线段树** 或 **稀疏表** 查询区间最大值，然后对于每个i，查询其区间[i-k, i+k]的最高站索引，再把V[i]加给它。 这样 O(N log N) 可过N=1e6吗？ - 线段树：O(N log N) 可能有点紧张但可优化。 - 稀疏表：O(1)查询，但空间 O(N log N) 会爆内存（1e6 * 20 ≈ 20M个int，可以接受）。 **由于题目数据 N=1e6，H和V都在int范围，但接收能量累加可能超过int，用long long。** --- ## 🚀 最终推荐解法：稀疏表（Sparse Table） ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10; int H[MAXN], V[MAXN]; long long receive[MAXN]; int st[MAXN][20]; // st[i][j] 存储区间[i, i+2^j-1]内最高H的索引 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, k; cin >> N >> k; for (int i = 1; i <= N; i++) { cin >> H[i] >> V[i]; st[i][0] = i; } // 构建稀疏表 for (int j = 1; (1 << j) <= N; j++) { for (int i = 1; i + (1 << j) - 1 <= N; i++) { int a = st[i][j-1]; int b = st[i + (1 << (j-1))][j-1]; st[i][j] = (H[a] > H[b]) ? a : b; } } auto query = [&](int l, int r) { int len = r - l + 1; int k = 31 - __builtin_clz(len); int a = st[l][k]; int b = st[r - (1 << k) + 1][k]; return (H[a] > H[b]) ? a : b; }; for (int i = 1; i <= N; i++) { int l = max(1, i - k); int r = min(N, i + k); int idx = query(l, r); receive[idx] += V[i]; } long long ans = 0; for (int i = 1; i <= N; i++) { if (receive[i] > ans) ans = receive[i]; } cout << ans << "\n"; return 0; } ``` --- ## 🧠 复杂度分析 - **时间**：构建稀疏表 O(N log N)，查询 O(N)。对于 N=1e6，log₂(1e6) ≈ 20，总操作约 2e7，可过。 - **空间**：st 数组 N * 20 ≈ 20e6 int，约80MB，在256MB限制内。 --- ## ⚡ 开发建议 1. **优先用long long**：累加和可能超过int，尤其N很大时。 2. **使用 `__builtin_clz`** 快速计算log2，避免浮点。 3. **IO加速**：`ios::sync_with_stdio(false); cin.tie(nullptr);` 能显著提升速度。 4. **若追求极致性能**：可用单调队列 O(N) 解法，但实现细节更多，稀疏表已足够。 --- ######[AI写代码神器 | 3118点数解答 | 2026-07-07 20:13:55]