滑动窗口最大值与最大工作效率问题的C++解法

我来为你解决这两个问题。首先从第一个问题开始，因为已经给出了暴力解法，我会直接展示优化后的单调队列解法，然后解决第二个问题。 ## 📝 问题一：P3397 滑动窗口最大值（单调队列优化版） ```cpp #include <iostream> #include <vector> #include <deque> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> arr(n); for (int i = 0; i < n; ++i) { cin >> arr[i]; } deque<int> dq; // 存储下标，保持单调递减 // 处理前k个元素 for (int i = 0; i < k; ++i) { while (!dq.empty() && arr[i] >= arr[dq.back()]) { dq.pop_back(); } dq.push_back(i); } // 输出第一个窗口的最大值 cout << arr[dq.front()] << endl; // 处理剩余窗口 for (int i = k; i < n; ++i) { // 移除不在窗口内的元素 if (!dq.empty() && dq.front() <= i - k) { dq.pop_front(); } // 维护单调队列 while (!dq.empty() && arr[i] >= arr[dq.back()]) { dq.pop_back(); } dq.push_back(i); // 输出当前窗口最大值 cout << arr[dq.front()] << endl; } return 0; } ``` ### 🎯 算法说明 - **时间复杂度**：$O(n)$，每个元素最多入队出队各一次 - **空间复杂度**：$O(k)$，队列最多存储k个元素 - **核心思想**：使用双端队列维护一个**单调递减队列**，队首始终是当前窗口的最大值 --- ## 📝 问题二：P3396 最大效率（动态规划解法） ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, K; cin >> N >> K; vector<long long> efficiency(N + 1); for (int i = 1; i <= N; ++i) { cin >> efficiency[i]; } // dp[i] 表示考虑前i个工人能获得的最大效率 vector<long long> dp(N + 1, 0); // 前缀和，方便计算区间和 vector<long long> prefixSum(N + 1, 0); for (int i = 1; i <= N; ++i) { prefixSum[i] = prefixSum[i - 1] + efficiency[i]; } for (int i = 1; i <= N; ++i) { // 不选择第i个工人 dp[i] = dp[i - 1]; // 选择连续j个工人（1 <= j <= min(K, i)） for (int j = 1; j <= min(K, i); ++j) { // 选择连续的j个工人：i-j+1 到 i // 那么第i-j个工人一定不能选（因为会超过K个连续） // 所以从前i-j-1个工人中选 long long current = (i - j - 1 >= 0 ? dp[i - j - 1] : 0) + (prefixSum[i] - prefixSum[i - j]); dp[i] = max(dp[i], current); } } cout << dp[N] << endl; return 0; } ``` ### 🎯 算法说明 - **时间复杂度**：$O(N \times K)$，对于大数据可能较慢 - **空间复杂度**：$O(N)$ - **DP状态定义**：`dp[i]`表示考虑前i个工人能获得的最大效率 ### 🚀 优化版本（使用单调队列优化为O(N)） ```cpp #include <iostream> #include <vector> #include <deque> #include <algorithm> using namespace std; int main() { int N, K; cin >> N >> K; vector<long long> efficiency(N + 1); for (int i = 1; i <= N; ++i) { cin >> efficiency[i]; } // 前缀和 vector<long long> prefixSum(N + 1, 0); for (int i = 1; i <= N; ++i) { prefixSum[i] = prefixSum[i - 1] + efficiency[i]; } // dp[i] 表示考虑前i个工人能获得的最大效率 vector<long long> dp(N + 1, 0); // 单调队列优化 deque<int> dq; // 存储下标 for (int i = 1; i <= N; ++i) { // 先计算dp[i] = dp[i-1]（不选第i个工人） dp[i] = dp[i - 1]; // 计算选择连续工人的情况 // dp[i] = max(dp[i - j - 1] + prefixSum[i] - prefixSum[i - j]) // 对于j从1到min(K, i) // 变换：dp[i] = prefixSum[i] + max(dp[i - j - 1] - prefixSum[i - j]) // 在队列中加入当前i的候选值 if (i - 1 >= 0) { // 计算候选值：dp[i-2] - prefixSum[i-1]（对应j=1） long long candidate = (i >= 2 ? dp[i - 2] : 0) - prefixSum[i - 1]; // 维护单调递减队列 while (!dq.empty() && (dp[dq.back() - 1] - prefixSum[dq.back()]) <= candidate) { dq.pop_back(); } dq.push_back(i - 1); } // 移除超出范围的元素（窗口大小为K） while (!dq.empty() && dq.front() < i - K) { dq.pop_front(); } // 如果队列不为空，更新dp[i] if (!dq.empty()) { int idx = dq.front(); dp[i] = max(dp[i], prefixSum[i] + dp[idx - 1] - prefixSum[idx]); } } cout << dp[N] << endl; return 0; } ``` ### 📊 方案对比 | 方案 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | 基础DP | $O(N \times K)$ | $O(N)$ | N较小或K较小时 | | 单调队列优化DP | $O(N)$ | $O(N)$ | 大规模数据 | ### 💡 开发建议 1. **注意数据类型**：效率和可能很大，使用 `long long` 避免溢出 2. **边界条件**：特别注意当 `i < K` 和 `i - j - 1 < 0` 等边界情况 3. **代码可读性**：添加详细的注释说明DP状态转移逻辑 ### 🎯 核心算法思想 对于第二题，核心的DP状态转移方程是： - **不选当前工人**：`dp[i] = dp[i-1]` - **选连续j个工人**：`dp[i] = max(dp[i-j-1] + sum(i-j+1...i))`，其中 $1 \le j \le min(K, i)$ 这样保证了任何连续选择的工人数不会超过K个。 ######[AI写代码神器 | 1739点数解答 | 2026-08-15 16:13:42]