A15083 | $Binary Deque$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出