牛客4577题解：滑动窗口解法

一、题目解读

牛客4577题要求处理多组测试数据，每组包含一个整数数组crimes和两个参数n（数组长度）、t（阈值）、c（窗口大小）。题目需要统计数组中所有长度恰好为c的子数组，其元素和不超过t的数量。该问题考察滑动窗口算法在子数组求和与计数中的应用，需高效处理数据以避免超时。

二、解题思路

采用滑动窗口+前缀和优化的核心思路。传统方法需遍历所有子数组计算和，时间复杂度为O(n^2)。但通过滑动窗口，可固定窗口右边界，动态调整左边界，仅用O(1)时间更新窗口和，从而将总时间复杂度降至O(n)。关键在于利用窗口的移动规律，结合“当前和-移出元素+新元素”的更新公式，避免重复计算。

三、解题步骤

1. 处理多组测试数据：通过while(cin >> n >> t >> c)循环读取每组数据，并初始化数组crimes。

2. 初始化窗口和计数器：

    定义count记录符合条件的窗口数量。

    定义window_sum初始化为前c个元素之和（即第一个窗口的和）。

    若window_sum <= t，则首个窗口符合条件，count++。

3. 滑动窗口移动逻辑，从第c个元素开始，每次右移窗口：

    更新窗口和：window_sum -= crimes[i - c] + crimes[i]（减去左边界移出元素，加上新进入元素）。

    若更新后的window_sum <= t，则当前窗口符合条件，count++。

4. 输出结果：每组数据结束后输出count，换行处理下一组。

四、代码与注释

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, t, c;
    while (cin >> n >> t >> c) {  // 处理多组测试数据
        vector<int> crimes(n);
        for (int i = 0; i < n; ++i) {
            cin >> crimes[i];  // 读取每个罪犯的罪行值
        }
        int count = 0;  // 记录符合条件的窗口数量
        long long window_sum = 0;  // 当前窗口的和，使用long long防止溢出
        // 初始化第一个窗口
        for (int i = 0; i < c; ++i) {
            window_sum += crimes[i];
        }
        if (window_sum <= t) {
            count++;
        }
        // 滑动窗口：每次移动一位
        for (int i = c; i < n; ++i) {
            // 减去离开窗口的元素，加上新进入窗口的元素
            window_sum = window_sum - crimes[i - c] + crimes[i];
            if (window_sum <= t) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

五、总结

该解法通过滑动窗口技术巧妙解决子数组求和计数问题，关键在于利用窗口的动态更新机制，避免了暴力枚举的指数级时间复杂度。代码简洁高效，适用于处理大规模数据场景。此思路对理解滑动窗口算法在求和、计数类问题中的应用具有指导意义，适合算法竞赛或面试中的优化题型。