本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-16 14:48:01

题目翻译

给你一个 $n$ 个元素且只包含 $1$ 或 $0$ 两种元素的序列 $a$，以及一个正整数 $s$。
在一次操作中，你可以删掉第一个元素或最后的元素。
求使得剩下元素总和等于 $s$ 的最小操作次数。

思路

考虑到只能在首尾删元素，可以将问题转化为：
在数列 $a$ 中选择一个区间 $[l,r]$，使得 $\sum_l^r a_i = s$，并且这个区间必须是满足条件的区间中最长的。

暴力思路

显然可以暴力枚举每一个区间，前缀和 $O(1)$ 判断当前区间总和是否为 $s$，然后更新答案。
复杂度 $O(n^2)$。

优化

首先设数列第 $i$ 个元素的前缀和是 $qzh_i$。
枚举左端点的部分不太好优化，那就优化选择右端点的部分。
显然，固定了左端点 $l$ 后，右端点 $r$ 的前缀和值 $qzh_r$ 也就固定了。可以将其算出来，等于 $qzh_{l-1} + s$。
而前缀和数组是升序的！
也就是说可以用 lower_bound，$O(\log n)$ 把右端点求出来。
但是要注意，lower_bound 求出来的右端点 $r$，是第一个满足要求的 $r$，而因为要求区间最长，我们需要的是最后一个满足要求的 $r$，所以还要做一些处理。
算出 $a_r$ 后面有多少个元素 $0$，设有 $sum$ 个，将 $r$ 跳到 $r+sum - 1$，也就是这些 $0$ 元素的最后一个。
这道题就做完了。
复杂度 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=2e5+5;
	int t,n,s;
	int a[maxn];
	int qzh[maxn];\/\/前缀和
	int len[maxn];
    \/\/len[i] 代表第 i 个元素开始有多少个相邻的相同元素
	void main()
	{
		scanf("%d",&t);
		while(t--)
		{
			scanf("%d%d",&n,&s);
			for(int i=1;i<=n;i++)
			{
				scanf("%d",&a[i]);
				qzh[i]=qzh[i-1]+a[i];
			}
			for(int i=n;i>=1;i--)
			{
				if(i==n)
				{
					len[i]=1;
					continue;
				}
				if(a[i]==a[i+1])len[i]=len[i+1]+1;
				else len[i]=1;
			}
			if(qzh[n]<s)
			{
				printf("-1\n");
				continue;
			}
			int maxlen=0;
			for(int l=1;l<=n;l++)
			{
				int r=lower_bound(qzh+l,qzh+n+1,s+qzh[l-1])-qzh;
				if(a[r+1]==0&&r<n)r=r+1+len[r+1]-1;
				if(r==n+1)
				{
					continue;
				}
				maxlen=max(maxlen,r-l+1);
			}
			printf("%d\n",n-maxlen);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}