c++滑动窗口算法问题

Question

小民的成绩很差，写题的正确率低。现在，有一场考试，需要做一张包含n道选择题的过卷，为了帮助小民通过考试，只要求：在这张试卷中对于任意连续的k道题里至少有m个是对的，小民就可以及格。请问满足此条件k的最小值是多少？
输入格式
第一行输入两个整数n,m。
第二行输入 n 个整数。其中，第i个整数表示小陈第i道题的答题情况，1 表示正确，0表示错误。
输出格式
输出一个整数k，表示满足条件的最小段长。如果不存在满足条件的k，则输出-1。
输入样例:
6 2
0 0 1 0 0 1 输出样例:6

Answer 1

♥ 该回答参考ChatGPT，由吾为汝整理提供，如若有用，还请题主采纳！♥

这是一个滑动窗口算法的问题。滑动窗口算法可以用来解决一些连续子数组或子序列的问题。

对于这个问题，我们可以使用滑动窗口算法来找到满足条件的最小段长k。

首先，我们可以定义两个指针left和right，分别表示滑动窗口的左边界和右边界。初始时，left和right都指向第一个题目。

然后，我们可以使用一个变量count来记录当前窗口内正确答题的数量。我们可以遍历题目的答题情况，如果答题情况为1，则将count加1。

接下来，我们开始滑动窗口。如果当前窗口内正确答题的数量小于m，我们就将右边界right向右移动一位，并更新count。如果当前窗口内正确答题的数量大于等于m，我们就可以尝试缩小窗口的大小，将左边界left向右移动一位，并更新count。

在滑动窗口的过程中，我们可以记录每次窗口大小的长度，找到满足条件的最小段长k。

下面是使用C++实现滑动窗口算法的代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> answers(n);
    for (int i = 0; i < n; i++) {
        cin >> answers[i];
    }

    int left = 0, right = 0;
    int count = 0;
    int minLen = INT_MAX;

    while (right < n) {
        if (answers[right] == 1) {
            count++;
        }

        while (count >= m) {
            minLen = min(minLen, right - left + 1);
            if (answers[left] == 1) {
                count--;
            }
            left++;
        }

        right++;
    }

    if (minLen == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << minLen << endl;
    }

    return 0;
}

希望对你有帮助！如果有任何疑问，请随时提问。