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
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
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.
题义: 给一个 01 串 ,长度为 n, 只能从头或者尾部删除 , 问最少删除多少次 , 使得剩下的元素和为 s思路:
从每一个起始位置开始遍历, 对于每一个起始位置, 二分法找到他的对应的最长终止位置.
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define vi vector<int>
#define ull unsigned long long
#define i128 __int128
#define TEST
#define TESTS int T; cin >> T; while(T--)
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long
const int N = 1E+6;
using namespace std;
void Main() {
int n ,s;
cin >> n >> s;
vi a(n+1);
cin >> a[1];
L(i, 2, n) { // 前缀和
int num;
cin >> num;
a[i] = a[i-1] + num;
}
int ans = INF;
L(i, 1, n) { // 枚举起始点, 二分找终点
int lo = i, hi = n; // 在 i 到 n 的范围内二分
while(lo <= hi) { //当 lo == hi 时 ,可能出现区间长度正好比 k 多一 ,所以写 小于等于 多判断一次
int mid = lo + ((hi - lo) >> 1);
if(a[mid] - a[i - 1] <= s) { // 数组从 i 到 mid 的和不大于 k, 向上查找更长的
lo = mid + 1;
}
else { // 若区间长度正好比 k 多一 hi-- ,返回 hi
hi = mid - 1;
}
//cout << "i= " << i << " " << "lo= " << lo << " hi= " << hi << endl;
}
if(a[hi] - a[i - 1] != s) continue;
ans = min(ans, n - hi + i - 1); // 答案是总长度减去最长的区间的长度
}
cout << (ans == INF ? -1 : ans) << endl;
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
TESTS Main();
return 0;
}