滑动窗口求解连续k个守卫最大危险值总和及其C++高效实现

## 🎯 问题分析 **任务**：在 `n` 个守卫中，找出**连续**的 `k` 个人，使得他们的危险程度总和最大，并输出这个最大总和。 **关键点**： - 必须是**连续**的 `k` 个人 - 求这段连续区间的最大危险值总和 - 数据范围：`1 ≤ k ≤ n ≤ 100000`，`a[i] ≤ 1000` --- ## 💡 解法思路 ### 🔄 滑动窗口（双指针）方法 由于要求**连续 k 个**元素的最大和，最直接高效的方法是**滑动窗口**： 1. 先计算前 `k` 个元素的和作为初始窗口值。 2. 每次滑动窗口：减去窗口第一个元素，加上窗口后面的新元素。 3. 记录过程中出现的最大和。 **时间复杂度**：`O(n)`，只需一次遍历。 **空间复杂度**：`O(1)`，仅需常数额外空间。 --- ## ✍️ C++ 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // 计算初始窗口（前 k 个）的和 long long window_sum = 0; for (int i = 0; i < k; i++) { window_sum += a[i]; } long long max_sum = window_sum; // 滑动窗口遍历 for (int i = k; i < n; i++) { // 移动窗口：移除最左侧，加入最右侧 window_sum = window_sum - a[i - k] + a[i]; max_sum = max(max_sum, window_sum); } cout << max_sum << endl; return 0; } ``` --- ## 📖 关键点解释 | 步骤 | 说明 | |------|------| | **初始化** | 第一个窗口是下标 `0` 到 `k-1` 的元素和 | | **滑动过程** | 窗口右移一位：`window_sum = window_sum - a[i-k] + a[i]` | | **更新最大值** | 每次滑动后用 `max()` 比较并更新 `max_sum` | - **为什么用 `long long`？** 最大情况：`n=100000`，每个`a[i]=1000`，连续 `k=100000`，总和可达 `10^8`，虽然 `int` 也够（约 `2.1×10^9`），但使用 `long long` 更安全，避免潜在溢出风险。 - **边界条件**：`k=1` 时，窗口大小为1，求的是单个元素最大值；`k=n` 时，直接求所有元素和。 --- ## 🧪 测试示例 **输入：** ``` 5 3 1 2 3 4 5 ``` **输出：** ``` 12 ``` （连续3个最大为 `3+4+5=12`） **输入：** ``` 4 2 7 3 8 1 ``` **输出：** ``` 11 ``` （连续2个最大为 `3+8=11`） --- ## ⚠️ 开发建议与注意事项 1. **输入输出优化**：对于大规模数据（`n=100000`），使用 `ios::sync_with_stdio(false); cin.tie(0);` 提升速度，防止超时。 2. **考虑使用前缀和**：滑动窗口已是最优，无需额外优化。若需查询多次不同 `k`，可预先计算前缀和。 3. **避免使用暴力法**：双重循环求所有连续 `k` 个子数组会达到 `O(n*k)` 复杂度，在 `k≈n` 时可能超时。 4. **数据安全性**：始终用 `long long` 存储累加和，以防极端测试数据。 5. **代码规范**：使用 `const` 或明确变量名（如 `window_sum`、`max_sum`）提高可读性。 --- ## 📚 进阶扩展 - 若题目改为**非连续**的 `k` 个人，则只需排序取前 `k` 大求和，复杂度 `O(n log n)`。 - 若求**连续 k 个的最小和**，同理只需将比较方向反转。 - 若数据量极大（`n>10^7`）且 `k` 较小，可考虑使用 `deque` 实现**单调队列**优化，但本题 `n=100000` 无需此方案。 --- ######[AI写代码神器 | 1069点数解答 | 2026-07-31 20:15:17]