#include <bits/stdc++.h> using namespace std; const int MAX - AI写代码神器

好的，我们来重新审视这个问题。你贴出的代码（使用“找左边第一个更高的站”和“找右边第一个更高的站”的方法）是**不正确**的，它只能处理一些特殊情况，无法通过所有测试数据。我需要为你揭示这个方法的根本性错误，并提供一个**100%正确、高效且易于理解**的解决方案。 ### 🎯 你的代码为什么错了？你的核心思想是：“能量会流向左边或右边第一个比它高的站”。**这个物理直觉是错误的。** **反例（一击致命）：** ``` 位置: 0 1 2 3 高度: 10 5 20 3 V: 1 1 1 1 k = 2 ``` 我们来分析发射站 `1` （位置1，高度5）。 - **你的代码逻辑**： - `L[1]` （左边第一个更高站） = 位置0 （高度10）。 - `R[1]` （右边第一个更高站） = 位置2 （高度20）。 - 在比较时，`H[R[1]] > H[L[1]]` （20 > 10），所以你的代码会把能量给右边，即`receive[2] += V[1]`。 - **题目真正的含义（全局最高）**： - 发射站1的传递范围是 `[1-2, 1+2]` = `[-1, 3]`，有效范围是 `[0, 3]`。 - 在这个范围内，最高的站是位置2（高度20）。 - 能量应该给位置2。 **咦？这次的正确结果也是位置2！看起来没错？** 让我们再试一个真正的反例： ``` 位置: 0 1 2 3 4 高度: 8 5 10 2 9 V: 1 1 1 1 1 k = 2 ``` 分析发射站 `1` （位置1，高度5）。 - **你的代码逻辑**： - `L[1]` = 位置0 （高度8）。 - `R[1]` = 位置2 （高度10）。 - 比较：`H[R[1]] > H[L[1]]` （10 > 8）是 true，能量给位置2。 -> `receive[2] += 1`。 - **题目真正的含义（全局最高）**： - 发射站1的传递范围是 `[max(0, 1-2), min(4, 1+2)]` = `[0, 3]`。 - 在这个范围内，最高的站是位置2（高度10）。 - 能量应该给位置2。 **看来你代码的逻辑又对了？不，让我们看位置 `0` （高度8）。** - **你的代码逻辑**： - `L[0]` = -1 （左边没有更高的）。 - `R[0]` = 位置2 （高度10）。 - 因为左边没候选，检查右边：`R[0] - 0 = 2 <= k`。所以能量给位置2。 -> `receive[2] += 1`。 - **题目真正的含义（全局最高）**： - 发射站0的传递范围是 `[0, min(4, 0+2)]` = `[0, 2]`。 - 在这个范围内，最高的站是**位置0本身**（高度8）还是位置2（高度10）？**是位置2**，因为8 < 10。 **结果又对了？** 这让你有点困惑，好像代码逻辑在某种情况下是对的。但让我们看**位置 `3` （高度2）**。 - **你的代码逻辑**： - `L[3]` = 位置2 （高度10）。 - `R[3]` = 位置4 （高度9）。 - 左边候选存在且 `3 - 2 = 1 <= k` （True）。 - 右边候选存在且 `4 - 3 = 1 <= k` （True），且 `H[R[3]]` （9） > `H[L[3]]` （10）是 **False** （9 > 10 为假）。 - 你的代码认为：`else { receive[leftCandidate] += V[i]; }`，能量给位置2。 -> `receive[2] += 1`。 - **题目真正的含义（全局最高）**： - 发射站3的传递范围是 `[max(0, 3-2), min(4, 3+2)]` = `[1, 4]`。 - 在 `[1, 4]` 这个范围内，高度分别为：`[5, 10, 2, 9]`。**最高的是位置2（高度10）**。 - 能量应该给位置2。 **看吧，这次你的代码又给了位置2，看起来是对的。** **一下，为什么你的代码看起来很“对”？** 因为局部性原理在这里产生了误导。在简单的反例中，`[i-k, i+k]` 范围内的最高站，**往往**就是左边或右边第一个比它高的站之一，或者是自己。你的代码恰好覆盖了这种情况，让你误以为它是正确的。 **真正的反例（一个足够刁钻的案例就能让你彻底失败）：** ``` 位置: 0 1 2 3 4 5 高度: 1 9 2 8 3 10 V: 1 1 1 1 1 1 k = 3 ``` 分析发射站 `2` （位置2，高度2）。 - **你的代码逻辑**： - `L[2]` = 位置1 （高度9）。 - `R[2]` = 位置3 （高度8）。 - 比较：`H[R[2]]` （8） > `H[L[2]]` （9）是 **False**。所以能量会给左边，即位置1。 -> `receive[1] += 1`。 - **题目真正的含义（全局最高）**： - 发射站2的传递范围是 `[max(0, 2-3), min(5, 2+3)]` = `[0, 5]`。 - 在 `[0, 5]` 这个范围内，最高的站是**位置5**（高度10）！！！位置1和位置3都不是最高的。 - 能量应该给**位置5**。 **你的代码给出的答案是位置1，而正确答案是位置5。这就是你代码的致命错误。** 它无法看到“远方”的、通过中间较矮的站传递过来的更高山峰。 --- ### 🚀 正确的解法：滑动窗口 + 单调队列既然题目要求的是“区间内最高”，那么针对每个发射站 `i`，找到 `[i-k, i+k]` 范围内最高的站，一个非常经典且高效的方法就是使用**双端队列（deque）维护一个单调递减队列**。 #### 🧠 核心思想 1. **将问题转化**：对于每个发射站 `i`，我们想找到以它为中心的窗口 `[i-k, i+k]` 内的最大高度。 2. **维护一个单调队列 `dq`**： - 这个队列存储的是窗口内站的下标。 - 队列中元素对应的 `H` 值是**严格递减**的。 - 队首元素就是当前窗口内最高站的下标。 3. **滑动窗口处理**： - 我们从左到右遍历所有发射站，想象有一个宽度为 `2k+1` 的滑动窗口在移动。 - 当我们处理到位置 `i` 时，`[i-k, i+k]` 这个窗口的右边界是 `i+k`。 - 我们只需要确保在移动过程中，窗口内的元素是有效的（即它们的下标在 `[i-k, i+k]` 内），并且单调队列正确更新。 #### 💡 算法步骤（详细） 1. **初始化**： - 一个双端队列 `dq`，用于存储下标。 - 一个数组 `receive` 用于累加能量。 2. **第一遍扫描（从左到右）**： - 我们不是为每个 `i` 都重新创建一个窗口，而是模拟窗口的滑动。 - `for (int i = 0; i < N; i++)`: - **移除过期的元素**：当 `dq` 的队首元素（最高站）的下标小于 `i - k` 时，说明它已经滑出了当前窗口的左半边，应该从队首弹出 (`pop_front`)。 - **维护单调性**：当新站 `i` 要加入窗口时，我们需要保证队列的单调递减性。只要 `H[dq.back()] <= H[i]`，就将队尾元素弹出 (`pop_back`)。**注意**：这里处理的是相等的情况，由于高度互不相同，`<=` 可以简写为 `<`，但保留 `<=` 更通用。 - **加入新站的下标**：`dq.push_back(i)`。 - **确定接收者**：现在，队首元素 `dq.front()` 就是 **当前窗口**`[i-k, i+k]`内最高的站。那么，对于**任意一个在这个窗口内的发射站**，只要它的能量还没被处理，我们就可以把能量累加到 `receive[dq.front()]`。但一个能量只能被处理一次，所以我们不能用这种方式。 **其实更简单的方法是直接对每个发射站 `j` 找它的接收者。我们可以通过记录每个站作为“接收者”时，它吸收了哪些能量。这要求我们为每个接收站 `r` 找到所有以 `r` 为中心的窗口内的发射站。这听起来复杂，但其实可以通过两次扫描（一次从左到右记录每个发射站左边最近的更高站，一次从右到左记录右边最近的更高站）来逼近，但之前证明这是错误的。** **这里给出一个更直接的、也是正确的代码。** 它可能不是最优的 `O(N)`，但它是正确且易于理解的，而且 `O(N^2)` 对于 `1e6` 肯定会超时。 **正确的 `O(N log N)` 解法：使用线段树或ST表进行区间最大值查询。** 对于每个发射站 `i`，查询区间 `[max(0, i-k), min(N-1, i+k)]` 内的最大值及其位置。这可以通过线段树轻松实现，复杂度 `O(N log N)`，对于 `1e6` 的数据量，线段树的空间开销约 `4 * 1e6 = 4MB`，非常完美。 #### 📝 完整代码（线段树实现） ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int H[MAXN], V[MAXN]; long long receive[MAXN]; struct SegmentTree { // 存储区间[L, R]内最大高度的位置下标 int tree[MAXN * 4]; void build(int node, int l, int r) { if (l == r) { tree[node] = l; return; } int mid = (l + r) >> 1; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); // 内部节点存储左右子节点中高度更高的那个位置 int leftPos = tree[node * 2]; int rightPos = tree[node * 2 + 1]; tree[node] = (H[leftPos] >= H[rightPos]) ? leftPos : rightPos; } // 查询区间 [ql, qr] 内最大高度的位置 int query(int node, int l, int r, int ql, int qr) { if (ql > r || qr < l) return -1; // 不在范围内 if (ql <= l && r <= qr) return tree[node]; int mid = (l + r) >> 1; int leftPos = query(node * 2, l, mid, ql, qr); int rightPos = query(node * 2 + 1, mid + 1, r, ql, qr); if (leftPos == -1) return rightPos; if (rightPos == -1) return leftPos; return (H[leftPos] >= H[rightPos]) ? leftPos : rightPos; } } segTree; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, k; cin >> N >> k; for (int i = 0; i < N; i++) { cin >> H[i] >> V[i]; } // 1. 建树 segTree.build(1, 0, N - 1); // 2. 处理每个发射站 for (int i = 0; i < N; i++) { int l = max(0, i - k); int r = min(N - 1, i + k); int receiver = segTree.query(1, 0, N - 1, l, r); receive[receiver] += V[i]; } // 3. 找最大值 long long ans = 0; for (int i = 0; i < N; i++) { ans = max(ans, receive[i]); } cout << ans << "\n"; return 0; } ``` ### 📊 算法复杂度与对比 | 解决方案 | 时间复杂度 | 空间复杂度 | 正确性 | 代码复杂度 | 推荐指数 | | :--- | :--- | :--- | :--- | :--- | :--- | | **你的方法（找左右第一个更高）** | O(N) | O(N) | ❌ 错误 | 低 | ⭐ | | **暴力查询** | O(N*k) | O(1) | ✅ 正确 | 极低 | ⭐ | | **线段树（本题推荐）** | **O(N log N)** | **O(N)** | ✅ 正确 | 中 | **⭐⭐⭐⭐** | | **ST表 (Sparse Table)** | O(N log N) | O(N log N) | ✅ 正确 | 中 | ⭐⭐⭐ (空间大，1e6可能会MLE) | | **双端队列滑动窗口（正确实现）** | **O(N)** | **O(N)** | ✅ 正确 | 中高 | **⭐⭐⭐⭐⭐** (理论最优，但实现细节较多) | ### 💡 开发建议与 1. **不要被“局部”迷惑**：当你感觉一个解法是基于“最近”或者“第一个”之类的局部性质时，一定要反问自己：“有没有可能远处的、更高的、被中间矮站阻挡的站才是真正的目标？” 这道题的能量传递实际上可以“越过”中间矮的站，直接到达远处更高的站，这是本题最关键的坑。 2. **区间查询第一反应**：当题目出现“区间`[L, R]`内的最大值/最小值/求和”这类描述时，你的第一反应应该是 **线段树**、**树状数组**（适用于求和）或 **ST表**（适用于静态区间最值，但不能修改）。线段树是最通用的。 3. **数据范围决定解法**：`N = 1e6` 是一个明确的信号。`O(N^2)` 完全不可行。`O(N log N)` 可行（线段树）。`O(N)` 可行但实现复杂。`O(N log N)` 且常数较小的线段树是本题的工程化最优解。 4. **代码细节**： - `long long` 的使用是正确的，防止累加溢出。 - `ios::sync_with_stdio(false); cin.tie(0);` 是竞赛必备的IO加速。 - 线段树的数组大小需要开 `4 * MAXN`，确保足够。 5. **学习资源**：线段树是算法竞赛的“万金油”，强烈建议掌握其原理和实现。可以搜索“线段树区间最值”或“线段树 OI Wiki”。 <bt>发射站能量接收问题：线段树区间查询的正确解法</bt> ######[AI写代码神器 | 3626点数解答 | 2026-07-05 11:15:06]

服务商

更多选项

快捷项

自定义