工厂工人效率最大化问题的代码修改与开发建议

### 😊问题分析 代码出现 `WA`（Wrong Answer）的原因可能在于状态转移方程或者单调队列维护部分存在错误。本题的核心是找到一种安排工人工作的方案，使得总效率最大且没有连续超过 `K` 名工人一起工作。我们使用动态规划和单调队列来优化时间复杂度。 ### 📝代码修改 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; int n, k; long long efficiency[MAXN], prefixSum[MAXN], dp[MAXN]; int q[MAXN]; // 单调队列 int main() { cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> efficiency[i]; prefixSum[i] = prefixSum[i - 1] + efficiency[i]; } int hh = 0, tt = -1; q[++tt] = 0; for (int i = 1; i <= n; ++i) { // 移除超出窗口范围的元素 while (hh <= tt && q[hh] < i - k) ++hh; // 更新 dp[i] dp[i] = dp[i - 1]; dp[i] = max(dp[i], dp[q[hh]] + prefixSum[i] - prefixSum[q[hh]]); // 维护单调队列的单调性 while (hh <= tt && dp[q[tt]] <= dp[i]) --tt; q[++tt] = i; } cout << dp[n] << endl; return 0; } ``` ### 📋修改说明 1. **窗口范围的判断**：在移除超出窗口范围的元素时，原代码判断的是 `q[hh] < i - k - 1`，这会导致窗口范围错误，应该改为 `q[hh] < i - k`，确保窗口大小不超过 `K`。 2. **状态转移方程**：原代码在更新 `dp[i]` 时，没有考虑到不选择第 `i` 个工人的情况，应该先将 `dp[i]` 初始化为 `dp[i - 1]`，再取最大值更新。 3. **单调队列的维护**：在维护单调队列的单调性时，原代码比较的是 `dp[q[tt]] <= dp[i - 1]`，应该改为 `dp[q[tt]] <= dp[i]`，确保队列的单调性正确。 ### ⭐开发建议 - **边界条件检查**：在处理窗口范围和初始化时，要仔细检查边界条件，避免出现越界错误。 - **逻辑清晰**：动态规划的状态转移方程要清晰明确，每一步的更新都要有合理的逻辑。 - **调试技巧**：可以使用输出中间结果的方式来调试代码，观察状态转移和队列的变化情况。 ######[AI写代码神器 | 694点数解答 | 2026-08-15 16:18:14]