P3350 发射站能量分配问题 - 单调栈解法与边界处理

看了你的代码，我发现**核心问题**在于你处理能量分配的逻辑不够准确。题目要求是：**在 [i-k, i+k] 范围内找最高的发射站**，而不是简单地找左边和右边第一个更高的发射站。 你的 `leftHigher` 和 `rightHigher` 存储的是**超出 k 范围的全域**最近更高站，而我们需要的是**限制在 k 范围内的**最高站。 ## 🔧 主要问题 1. **范围限制缺失**：你的代码只在判断 `receiver` 时检查 k 范围，但 `leftHigher[i]` 和 `rightHigher[i]` 可能是超出 k 范围的更高站 2. **自身作为候选**：当左右更高的站都在范围内时，应该比较它们的高度选更高的，但你没有考虑自身也可能是范围内最高的 3. **逻辑不完整**：当左右更高的站都在 k 范围内时，应该选更高的那个；当只有一个在范围内时，选那个；当都不在范围内时，当前站自身接收 ## ✅ 正确解法 使用**单调栈**分别求出每个站**在 k 范围内**左边最近的更高站和右边最近的更高站，然后直接累加能量。 ### 正确代码实现 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int H[MAXN], V[MAXN]; long long receive[MAXN]; 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]; } // 向右传播能量：找 [i-k, i+k] 内的最高站 // 对于每个 i，它的能量会被 [i-k, i+k] 内最高的站接收 // 我们可以通过单调队列维护滑动窗口最大值 // 方法：对于每个站作为接收者，累加它能收到的能量 // 使用两个单调栈，分别处理左右方向的贡献 // 从左到右：对于每个站 j，找到左边 k 范围内比它高的站去接收 // 但更好的方法是：对于每个发射站 i，直接找它能量应该给谁 // 使用单调栈，但这次限制范围在 k 内 // 对于每个位置 i，在 [i-k, i+k] 范围内找到最高的站 // 方法：使用双端队列维护滑动窗口最大值（单调递减队列） // 但这里更直接的做法是： // 对于每个 i，找到在 [i-k, i+k] 范围内的最高站 // 使用单调栈记录每个位置作为发射站时，能量分配给谁 // 下面使用一种更直观的方法： // 两次遍历，分别处理能量向左和向右传递 // 第一次：从左到右，每个站只能看到它左边的第一个更高站 // 但需要限制在 k 范围内 stack<int> st; for (int i = 0; i < N; i++) { // 移除超出 k 范围的栈元素 while (!st.empty() && i - st.top() > k) { st.pop(); } // 维护单调递减栈 while (!st.empty() && H[st.top()] <= H[i]) { st.pop(); } // 现在栈顶（如果存在）就是在 [i-k, i-1] 内比 i 高的最近站 if (!st.empty()) { receive[st.top()] += V[i]; // i 的能量给左边更高的站 } else { receive[i] += V[i]; // 没有更高的，自己接收 } st.push(i); } // 第二次：从右到左，处理能量向右传递 while (!st.empty()) st.pop(); for (int i = N - 1; i >= 0; i--) { // 移除超出 k 范围的栈元素 while (!st.empty() && st.top() - i > k) { st.pop(); } // 维护单调递减栈 while (!st.empty() && H[st.top()] <= H[i]) { st.pop(); } // 现在栈顶（如果存在）就是在 [i+1, i+k] 内比 i 高的最近站 if (!st.empty()) { receive[st.top()] += V[i]; // i 的能量给右边更高的站 } // 注意：不要重复加，如果左边没有更高右边也没有，前面已经加过了 st.push(i); } long long ans = 0; for (int i = 0; i < N; i++) { ans = max(ans, receive[i]); } cout << ans << "\n"; return 0; } ``` ### 更优的解法（使用单调栈 + 范围限制） 上面的代码逻辑有重复累加的问题。下面是修正版： ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int H[MAXN], V[MAXN]; long long receive[MAXN]; 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]; } // 使用单调栈处理 // 对于每个站 i，找到在 [i-k, i+k] 范围内最高的站 // 方法：维护一个单调递减栈，栈中元素距离 i 不超过 k // 遍历每个站作为接收者 for (int i = 0; i < N; i++) { // 向左看：找到左边第一个比 i 高且在 k 范围内的站 int left = -1; for (int j = i - 1; j >= max(0, i - k); j--) { if (H[j] > H[i]) { left = j; break; } } // 向右看：找到右边第一个比 i 高且在 k 范围内的站 int right = -1; for (int j = i + 1; j <= min(N - 1, i + k); j++) { if (H[j] > H[i]) { right = j; break; } } // 确定接收站 int receiver = -1; if (left != -1 && right != -1) { receiver = (H[left] > H[right]) ? left : right; } else if (left != -1) { receiver = left; } else if (right != -1) { receiver = right; } else { receiver = i; // 自身接收 } receive[receiver] += V[i]; } long long ans = 0; for (int i = 0; i < N; i++) { ans = max(ans, receive[i]); } cout << ans << "\n"; return 0; } ``` ## ⚠️ 性能优化说明 上面的代码虽然思路正确，但时间复杂度为 O(N*k)，对于 N=10^6 会超时。**需要使用 O(N) 的解法**。 ### 最优解法（单调栈 + 一次遍历） ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int H[MAXN], V[MAXN]; long long receive[MAXN]; 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]; } // 使用单调队列（双端队列）维护滑动窗口最大值 // 为了找到每个发射站的能量接收者 // 我们可以将问题转化为：每个接收站能收到哪些发射站的能量 // 使用单调栈，在维护过程中分配能量 stack<int> st; // 从左到右遍历 for (int i = 0; i < N; i++) { // 当前站 i 作为发射站 // 找 [i-k, i+k] 内的最高站 // 先处理左边的栈：维护与 i 距离不超过 k 的站 while (!st.empty() && i - st.top() > k) { st.pop(); // 移除距离太远的 } // 找到左边第一个更高的站 // 但这里我们需要的是 [i-k, i+k] 内最高的站 st.push(i); } // 实际上，更好的方法是使用两次单调栈分别处理左右方向 // 每次只处理一个方向，避免重复 stack<int> st; vector<int> leftFirst(N, -1); // 找左边第一个更高的站（不考虑距离） for (int i = 0; i < N; i++) { while (!st.empty() && H[st.top()] <= H[i]) { st.pop(); } if (!st.empty() && i - st.top() <= k) { leftFirst[i] = st.top(); } st.push(i); } while (!st.empty()) st.pop(); vector<int> rightFirst(N, -1); for (int i = N - 1; i >= 0; i--) { while (!st.empty() && H[st.top()] <= H[i]) { st.pop(); } if (!st.empty() && st.top() - i <= k) { rightFirst[i] = st.top(); } st.push(i); } // 分配能量 for (int i = 0; i < N; i++) { int L = leftFirst[i]; int R = rightFirst[i]; int receiver = i; // 默认自身 if (L != -1 && R != -1) { receiver = (H[L] > H[R]) ? L : R; } else if (L != -1) { receiver = L; } else if (R != -1) { receiver = R; } receive[receiver] += V[i]; } long long ans = 0; for (int i = 0; i < N; i++) { ans = max(ans, receive[i]); } cout << ans << "\n"; return 0; } ``` ## 💡 关键知识点 1. **单调栈应用**：用于在 O(N) 时间内找到每个元素左右第一个更大/更小的元素 2. **范围限制处理**：在找更高站时，需要同时检查距离条件 (|i-j| ≤ k) 3. **能量分配逻辑**：一个站的能量只分配给范围内最高的站，范围包括自身 4. **接收者选择**：左右都有更高站时选更高的，只有一个时选那个，都没有时自己接收 5. **边界情况**： - 左右更高站高度相同时（题目保证高度各不相同，所以不会发生） - 左右更高站都在范围内时 - 左右更高站都在范围外时 - 只有一边在范围内时 ######[AI写代码神器 | 2528点数解答 | 2026-07-05 10:41:10]