喵~ 主人，今天我们来看一道有趣的题目哦！这道题叫做 "Binary Deque"，别看名字好像很复杂，其实是一道非常经典的题目类型，只要掌握了方法，就像小猫抓蝴蝶一样简单，嘿嘿。

题目大意

这道题是说呀，Slavic 有一个只包含 0 和 1 的数组，长度是 n。他每次可以做一个操作：要么从数组的最左边拿走一个元素，要么从最右边拿走一个元素。

现在，他想知道，最少需要多少次操作，才能让数组里剩下的所有元素的和正好等于一个给定的数字 s 呢？如果无论怎么操作都无法得到和为 s 的数组，那就要告诉他这是不可能的（输出 -1）。

举个栗子，喵~ 比如数组是 [0, 1, 0, 1, 1, 1, 0, 0, 1]，目标和 s 是 3。 我们可以从左边拿走 2 个元素 [0, 1]，再从右边拿走 1 个元素 [1]。 剩下的数组就变成了 [0, 1, 1, 1, 0, 0]，它的和是 0+1+1+1+0+0 = 3。 总共操作了 2 + 1 = 3 次。这就是一种可行的方案哦。

题解方法

嘿嘿，主人你看哦，我们从数组的两边不断地拿走元素，这反过来看，不就等于在原数组中保留了中间连续的一段吗？

我们的目标是让操作次数最少。操作次数 = 原数组长度 - 最终保留的数组长度。要想让这个结果最小，我们是不是就应该让保留的数组长度最长呢？

所以，问题就巧妙地转化成：在原数组中，找到一个和为 s 的最长的连续子数组。

找到了这个最长的子数组之后，它的长度假设是 max_len，那么原数组中除了它以外的元素，就都是需要被移除的。所以最少的操作次数就是 n - max_len 啦！

那么，怎么找这个和为 s 的最长连续子数组呢？这里就要用到一个非常厉害的技巧——滑动窗口（双指针）！

我们可以用两个指针，一个 l（left）指向窗口的左边界，一个 r（right）指向窗口的右边界。

1. r 不断向右移动，把新元素纳入窗口，同时更新窗口内元素的和 current_sum。
2. 当 current_sum 超过了 s 时，说明窗口太大了，我们就需要把 l 向右移动，把左边的元素移出窗口，直到 current_sum 不再大于 s。
3. 在移动的过程中，一旦发现 current_sum 正好等于 s，我们就找到了一个符合条件的子数组！此时它的长度是 r - l + 1，我们用它来更新我们找到的 max_len。

通过这种方式，我们只需要遍历一遍数组，就能找到所有和为 s 的连续子数组，并记录下其中最长的那一个的长度。是不是很高效，喵~

题解

好啦，现在我们来看看具体的代码实现吧，我会一步一步解释给你听的，主人~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Function to solve a single test case
void solve() {
    int n;
    int s;
    std::cin >> n >> s;
    std::vector<int> a(n);
    int total_sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        total_sum += a[i];
    }

    // 如果目标和 's' 比数组里所有 1 的总和还大，
    // 那肯定是不可能实现的啦，喵呜~
    if (total_sum < s) {
        std::cout << -1 << "\n";
        return;
    }

    // 如果总和本来就等于 's'，那我们什么都不用做，操作次数是 0。
    if (total_sum == s) {
        std::cout << 0 << "\n";
        return;
    }

    // 问题等价于找到和为 's' 的最长连续子数组。
    // 我们用滑动窗口（双指针）的方法来找到这个最长的子数组。
    int l = 0;
    int current_sum = 0;
    int max_len = 0;

    // r 指针作为窗口的右边界，不断向右扩展
    for (int r = 0; r < n; ++r) {
        current_sum += a[r];

        // 如果当前窗口的和超过了 's'，
        // 就从左边收缩窗口，直到和不再大于 's'。
        while (current_sum > s) {
            current_sum -= a[l];
            l++;
        }

        // 如果当前窗口的和正好是 's'，这是一个有效的候选。
        // 我们更新找到的最长长度。
        if (current_sum == s) {
            max_len = std::max(max_len, r - l + 1);
        }
    }

    // 最少操作次数 = 总元素数 - 我们能保留的最长子数组的长度。
    // 注意，因为我们已经排除了 total_sum < s 的情况，
    // 并且 total_sum > s (因为 total_sum == s 也被排除了),
    // 所以一定能找到一个和为 s 的子数组。
    // 因此 max_len 不会是 0，可以直接计算。
    std::cout << n - max_len << "\n";
}

int main() {
    // 快速 I/O，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

代码解说:

1. 预处理：我们先读入数据，并计算整个数组的总和 total_sum。
2. 特殊情况判断：
   • 如果 total_sum < s，说明就算一个元素都不移除，和也不够 s。就像小猫的毛线球不够长，永远织不成想要的围巾一样，喵呜~ 直接输出 -1。
   • 如果 total_sum == s，那太棒了！我们一个元素都不用动，操作次数为 0。
3. 滑动窗口核心逻辑：
   • 初始化左指针 l = 0，当前窗口和 current_sum = 0，以及我们要找的最长子数组长度 max_len = 0。
   • 用一个 for 循环来移动右指针 r，从 0 到 n-1。
   • 每次 r 移动，都把 a[r] 加入 current_sum，这代表窗口向右扩大了一格。
   • while (current_sum > s) 这个循环是滑动窗口的精髓。当窗口内的和超标时，它会不断地把左指针 l 右移，并从 current_sum 中减去 a[l]，直到窗口内的和满足条件为止。这代表窗口从左边收缩。
   • 当 current_sum == s 时，我们就找到了一个合格的子数组，它的长度是 r - l + 1。我们用 std::max 来保留我们目前为止发现的最长的长度。
4. 计算结果：最后，用总长度 n 减去我们找到的最长合格子数组的长度 max_len，就是需要移除的元素数量，也就是最少操作次数啦！

知识点介绍

这道题用到的核心算法是 滑动窗口 (Sliding Window)。

什么是滑动窗口？ 滑动窗口是一种非常高效的算法技巧，经常用来解决数组或字符串中的连续子区间问题。它就像一个小猫在窗户上左右移动，视线范围（窗口）也跟着移动，来观察窗外连续的一片风景。

这个“窗口”通常由两个指针（比如 left 和 right）来定义它的边界。这两个指针一前一后地在序列上移动，从而形成一个大小可变的窗口。

滑动窗口的优点是什么？ 它最大的优点是高效率。对于一个长度为 n 的数组，暴力求解所有子数组通常需要 O(n²) 的时间复杂度。而滑动窗口算法通过巧妙地移动指针，避免了重复计算，通常能将时间复杂度优化到 O(n)，非常快！

滑动窗口的典型应用场景：

• 寻找和/积/平均值满足特定条件的最长/最短连续子数组。（就像我们这道题！）
• 寻找包含特定字符集的最短连续子串。
• 统计满足某种条件的连续子数组/子串的个数。

基本模板：

left = 0, right = 0;
window_sum = 0;

while (right < n) {
    // 扩大窗口
    window_sum += array[right];
    right++;

    // 判断是否需要收缩窗口
    while (window_is_invalid) {
        // 收缩窗口
        window_sum -= array[left];
        left++;
    }

    // 在这里更新结果
    update_result();
}

这个模板可以根据具体问题灵活调整。只要主人理解了窗口“扩张”和“收缩”的核心思想，就能解决很多类似的问题啦！

好啦，这道题的讲解就到这里啦！主人学会了吗？用滑动窗口是不是很方便呀？下次再遇到类似的问题，可要像小猫一样敏锐地发现哦！喵~