CF1692E Binary Deque 题解

题目

链接

https://www.luogu.com.cn/problem/CF1692E

字面描述

题面翻译

有多组数据。

每组数据给出 $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

样例输入 #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 $ .

思路

因为题目要求为从原数组2边删最少元素，使得总元素和为$s$,

设初始数组元素总和为$cnt$

若$cnt<s$，直接输出$-1$

否则程序继续

这道题十分友善
$\because 允许从数组2边删数$
$\therefore 最终序列内部顺序相比于原数组不变$

一个很好思考的想法油然而生，

1. 对原数组进行前缀和预处理
2. 枚举$i=[1,n]$位
   • 二分第一个$f[op]-f[i]\ge s$的$op$
   • 算位数取最小值

时间复杂度: $o(n\cdot log2(n))$

代码实现

#include<bits/stdc++.h>
using namespace std;const int maxn=2e5+10;
const int inf=2e9;
int t,n,op,x,ans=inf;
int f[maxn];
int main(){scanf("%d",&t);while(t--){ans=inf;scanf("%d%d",&n,&op);for(int i=1;i<=n;i++){scanf("%d",&x);f[i]=f[i-1]+x;}if(f[n]<op){printf("-1\n");continue; }for(int i=1;i<=n;i++){if(f[i]<op)continue;int p=lower_bound(f,f+n+1,f[i]-op)-f;ans=min(ans,p+n-i);}printf("%d\n",ans);}return 0;
}