当前位置:首页 > 牛客题解 > 牛客网4577题解:滑动窗口算法解决连续子序列问题

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

19小时前牛客题解45

截图未命名.jpg 牛客网4577题解:滑动窗口算法解决连续子序列问题 滑动窗口算法 算法实现 牛客网题解 C++ 第1张

一、问题重述

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

二、C++代码实现

#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;
}
// 64 位输出请用 printf("%lld")

三、算法核心思想

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

四、关键步骤解析

  1. 初始化窗口‌:计算前c个元素的和作为初始窗口

  2. 滑动过程‌:

    • 窗口右移一位

    • 减去最左边离开窗口的元素值

    • 加上新进入窗口的右边元素值

  3. 条件检查‌:每次更新窗口后检查总和是否≤t

五、算法优化空间

  1. 提前终止‌:如果发现某个窗口和>t,可以跳过后续检查

  2. 并行计算‌:对于超大n,可分块并行处理

  3. 预处理‌:构建前缀和数组可支持多种查询


原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。