牛客网4577题解：滑动窗口算法解决连续子序列问题

15303105423

一、问题重述

我们需要从n名按入狱时间排序的罪犯中，找出所有长度为c的连续子序列，使得这些子序列的罪行值之和不超过t。这是一个典型的滑动窗口问题，适合用高效算法解决。

二、C++代码实现

1. #include <iostream>
   
2. #include <vector>
   
3. using namespACe std;
   
4. 
   
5. int main() {
   
6.     int n, t, c;
   
7.     while (cin >> n >> t >> c) {  // 处理多组测试数据
   
8.         vector<int> crimes(n);
   
9.         for (int i = 0; i < n; ++i) {
   
10.             cin >> crimes[i];  // 读取每个罪犯的罪行值
    
11.         }
    
12. 
    
13.         int count = 0;  // 记录符合条件的窗口数量
    
14.         long long window_sum = 0;  // 当前窗口的和，使用long long防止溢出
    
15. 
    
16.         // 初始化第一个窗口
    
17.         for (int i = 0; i < c; ++i) {
    
18.             window_sum += crimes[i];
    
19.         }
    
20.         if (window_sum <= t) {
    
21.             count++;
    
22.         }
    
23. 
    
24.         // 滑动窗口：每次移动一位
    
25.         for (int i = c; i < n; ++i) {
    
26.             // 减去离开窗口的元素，加上新进入窗口的元素
    
27.             window_sum = window_sum - crimes[i - c] + crimes[i];
    
28.             if (window_sum <= t) {
    
29.                 count++;
    
30.             }
    
31.         }
    
32. 
    
33.         cout << count << endl;
    
34.     }
    
35.     return 0;
    
36. }
    
37. // 64 位输出请用 printf("%lld")

复制代码

三、算法核心思想

滑动窗口算法通过维护一个固定大小的"窗口"（这里是c名罪犯），在遍历数组时高效更新窗口内的信息。相比暴力解法（O(n²)时间复杂度），滑动窗口将复杂度降低到O(n)。

四、关键步骤解析

• ‌初始化窗口‌：计算前c个元素的和作为初始窗口
• ‌滑动过程‌：
  
  
  • 窗口右移一位
  • 减去最左边离开窗口的元素值
  • 加上新进入窗口的右边元素值
    
    
• ‌条件检查‌：每次更新窗口后检查总和是否≤t
  
  

五、算法优化空间

• ‌提前终止‌：如果发现某个窗口和>t，可以跳过后续检查
• ‌并行计算‌：对于超大n，可分块并行处理
• ‌预处理‌：构建前缀和数组可支持多种查询
  
  

来源：竞赛学习