优化工厂工人效率安排代码以避免超时问题

### 😥问题分析 原代码的时间复杂度是 $O(NK)$，在 $N$ 和 $K$ 较大时，可能会导致超时（TLE）。可以使用单调队列来优化内层循环，将时间复杂度降低到 $O(N)$。 ### 📝优化思路 使用单调队列来维护一个滑动窗口，窗口内存储的是可以用来更新 $dp$ 数组的候选位置。这样在每次更新 $dp[i]$ 时，就可以 $O(1)$ 的时间找到最优的候选位置。 ### 💻优化后的代码 ```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 - 1) ++hh; // 更新 dp[i] dp[i] = max(dp[i - 1], dp[q[hh]] + prefixSum[i] - prefixSum[q[hh]]); // 维护单调队列的单调性 while (hh <= tt && dp[q[tt]] <= dp[i - 1]) --tt; q[++tt] = i - 1; } cout << dp[n] << endl; return 0; } ``` ### 📌代码解释 1. **前缀和数组 `prefixSum`**：用于快速计算任意区间的效率和。 2. **单调队列 `q`**：用于维护一个滑动窗口，窗口内存储的是可以用来更新 $dp$ 数组的候选位置。 3. **更新 `dp` 数组**： - 对于每个 $i$，先移除超出窗口范围的元素。 - 然后更新 $dp[i]$，取不选择第 $i$ 个工人和选择连续工人的最大值。 - 最后维护单调队列的单调性，将 $i - 1$ 加入队列。 ### 🌟复杂度分析 - **时间复杂度**：$O(N)$，因为每个元素最多入队和出队一次。 - **空间复杂度**：$O(N)$，主要用于存储 $dp$ 数组和前缀和数组。 ######[AI写代码神器 | 653点数解答 | 2026-08-15 16:16:42]