牛客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;
}五、总结
该解法通过滑动窗口技术巧妙解决子数组求和计数问题，关键在于利用窗口的动态更新机制，避免了暴力枚举的指数级时间复杂度。代码简洁高效，适用于处理大规模数据场景。此思路对理解滑动窗口算法在求和、计数类问题中的应用具有指导意义，适合算法竞赛或面试中的优化题型。
原创内容 转载请注明出处
