Binary Deque

题意翻译

有多组数据。 每组数据给出 $n$ 个数，每个数为 $0$ 或 $1$ 。你可以选择从两边删数，求至少删几个数才可以使剩下的数总和为 $s$ 。 如果不能达到 $s$ ，则输出 $-1$ 。

题目描述

Slavic has an array of length $ n $ consisting only of zeroes and ones. In one operation, he removes either the first or the last element of the array. What is the minimum number of operations Slavic has to perform such that the total sum of the array is equal to $ s $ after performing all the operations? In case the sum $ s $ can't be obtained after any amount of operations, you should output -1.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ s $ ( $ 1 \leq n, s \leq 2 \cdot 10^5 $ ) — the length of the array and the needed sum of elements. The second line of each test case contains $ n $ integers $ a_i $ ( $ 0 \leq a_i \leq 1 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output a single integer — the minimum amount of operations required to have the total sum of the array equal to $ s $ , or -1 if obtaining an array with sum $ s $ isn't possible.

输入输出样例

输入样例 #1

7
3 1
1 0 0
3 1
1 1 0
9 3
0 1 0 1 1 1 0 0 1
6 4
1 1 1 1 1 1
5 1
0 0 1 1 0
16 2
1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1
6 3
1 0 1 0 0 0

输出样例 #1

0
1
3
2
2
7
-1

说明

In the first test case, the sum of the whole array is $ 1 $ from the beginning, so we don't have to make any operations. In the second test case, the sum of the array is $ 2 $ and we want it to be equal to $ 1 $ , so we should remove the first element. The array turns into $ [1, 0] $ , which has a sum equal to $ 1 $ . In the third test case, the sum of the array is $ 5 $ and we need it to be $ 3 $ . We can obtain such a sum by removing the first two elements and the last element, doing a total of three operations. The array turns into $ [0, 1, 1, 1, 0, 0] $ , which has a sum equal to $ 3 $ .

**题意翻译**

题目描述了多组数据，每组数据包含一个长度为 $ n $ 的只包含 0 和 1 的数组。你可以选择从数组的两端删除数字，目标是经过若干次操作后，使得数组中的数字总和等于 $ s $。如果无法通过删除操作达到总和为 $ s $，则输出 -1。

**题目描述**

斯拉夫有一个长度为 $ n $ 的数组，数组只包含 0 和 1。每次操作，他可以移除数组的首元素或尾元素。需要找出斯拉夫至少需要执行多少次操作，才能使得数组元素的总和等于 $ s $。如果无论如何操作都不能使数组总和达到 $ s $，则应输出 -1。

**输入输出格式**

**输入格式**

第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。

每个测试用例的第一行包含两个整数 $ n $ 和 $ s $（$ 1 \leq n, s \leq 2 \cdot 10^5 $）——数组的长度和需要的元素总和。

每个测试用例的第二行包含 $ n $ 个整数 $ a_i $（$ 0 \leq a_i \leq 1 $）——数组的元素。

保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

**输出格式**

对于每个测试用例，输出一个整数——使得数组总和等于 $ s $ 所需的最少操作次数，或者如果无法得到总和为 $ s $ 的数组，则输出 -1。

**输入输出样例**

**输入样例 #1**

```
7
3 1
1 0 0
3 1
1 1 0
9 3
0 1 0 1 1 1 0 0 1
6 4
1 1 1 1 1 1
5 1
0 0 1 1 0
16 2
1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1
6 3
1 0 1 0 0 0
```

**输出样例 #1**

```
0
1
3
2
2
7
-1
```

**说明**

第一个测试用例中，数组总和一开始就是 1，所以不需要进行任何操作。

第二个测试用例中，数组的总和是 2，我们需要它等于 1，所以应该移除第一个元素。数组变为 [1, 0]，其总和等于 1。

第三个测试用例中，数组的总和是 5，我们需要它等于 3。我们可以通过移除前两个元素和最后一个元素来达到这样的总和，总共进行三次操作。数组变为 [0, 1, 1, 1, 0, 0]，其总和等于 3。**题意翻译** 题目描述了多组数据，每组数据包含一个长度为 $ n $ 的只包含 0 和 1 的数组。你可以选择从数组的两端删除数字，目标是经过若干次操作后，使得数组中的数字总和等于 $ s $。如果无法通过删除操作达到总和为 $ s $，则输出 -1。 **题目描述** 斯拉夫有一个长度为 $ n $ 的数组，数组只包含 0 和 1。每次操作，他可以移除数组的首元素或尾元素。需要找出斯拉夫至少需要执行多少次操作，才能使得数组元素的总和等于 $ s $。如果无论如何操作都不能使数组总和达到 $ s $，则应输出 -1。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ s $（$ 1 \leq n, s \leq 2 \cdot 10^5 $）——数组的长度和需要的元素总和。 每个测试用例的第二行包含 $ n $ 个整数 $ a_i $（$ 0 \leq a_i \leq 1 $）——数组的元素。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，输出一个整数——使得数组总和等于 $ s $ 所需的最少操作次数，或者如果无法得到总和为 $ s $ 的数组，则输出 -1。 **输入输出样例** **输入样例 #1** ``` 7 3 1 1 0 0 3 1 1 1 0 9 3 0 1 0 1 1 1 0 0 1 6 4 1 1 1 1 1 1 5 1 0 0 1 1 0 16 2 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 6 3 1 0 1 0 0 0 ``` **输出样例 #1** ``` 0 1 3 2 2 7 -1 ``` **说明** 第一个测试用例中，数组总和一开始就是 1，所以不需要进行任何操作。 第二个测试用例中，数组的总和是 2，我们需要它等于 1，所以应该移除第一个元素。数组变为 [1, 0]，其总和等于 1。 第三个测试用例中，数组的总和是 5，我们需要它等于 3。我们可以通过移除前两个元素和最后一个元素来达到这样的总和，总共进行三次操作。数组变为 [0, 1, 1, 1, 0, 0]，其总和等于 3。