Location>code7788 >text

Two pointer exercises: Binary Deque

Popularity：953 ℃/2025-01-14 11:39:13

Deque

Title translation

Binary Deque - Luogu | New Ecosystem of Computer Science Education ()

There are multiple sets of data.

Each set of data is given\(n\)number, each number is\(0\)or\(1\). You can choose to delete numbers from both sides. Find at least how many numbers can be deleted so that the sum of the remaining numbers is\(s\) 。

if it cannot be achieved\(s\), then output\(-1\) 。

Question description

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.

Input format

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 $ .

Output format

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.

Example #1

Sample input #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

Sample output #1

0
1
3
2
2
7
-1

hint

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 $ .

Idea:

This question can use double pointers to dynamically obtain the optimal solution. We can first calculate the sum of all elements. If sum is less than s, it is impossible to achieve the goal. Output -1 and then process the next example. If s==sum , then the number of operations is exactly 0, you can output 0 and return directly. Otherwise, we use the idea of ​​​​dual pointers, here are fast and slow pointers, and we maintain a dynamic range.

  1. If the sum of the elements in this dynamic interval sum=s, then we update the answer at this time and let the fast pointer go to the right
  3. If the sum of the elements in this dynamic interval is >s, then we need to narrow the interval and find the optimal answer.

Code:


 using namespace std;
 const int N=2e5+10;
 int n,s;
 int a[N];
 void solve(){
     int n,s;
     cin>>n>>s;
     int sum=0;
     //First calculate the sum of all elements. If the sum of all elements is less than s, it is impossible to achieve the goal. If it is exactly equal to s, the number of operations is 0.
     for(int i=1;i<=n;i++){
         cin>>a[i];
         sum+=a[i];
     }
     if(sums){
             sum-=a[l];
             l++;
         }
     }
     cout<>t;
     while(t--) solve();
     return 0;
 }
<Previous