---

E. Binary Deque

原创 于 2023-08-27 15:38:40 发布 · 粉丝可见 · 146 阅读 · 0 · 1 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132524065

题目：

样例：

cobol<br/>7<br/>3 1<br/>1 0 0<br/>3 1<br/>1 1 0<br/>9 3<br/>0 1 0 1 1 1 0 0 1<br/>6 4<br/>1 1 1 1 1 1<br/>5 1<br/>0 0 1 1 0<br/>16 2<br/>1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1<br/>6 3<br/>1 0 1 0 0 0<br/>

0 1 3 2 2 7 -1

思路：

双指针，思维可模拟的题，这题目的意思是 只删除前面和后面，我们应该联想到 子序列

这里需要特判两个情况，最后难点就是在维护子序列的情况；

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;

inline void solve()
{
	umap<int, int>v;
	int ans = -1;
	int n, needSum, sum = 0;
	cin >> n >> needSum;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;
		v[i] = x;
		sum += x;
	}
	// 特判 如果数组总和小于，那么无论删减都无法完成
	if (sum < needSum)
	{
		puts("-1");
		return ;
	}
	// 特判 如果数组一开始就等于了，那么不用操作
	if (sum == needSum)
	{
		putchar('0');
		putchar('\n');
		return ;
	}

	// 由于是只删减前面和后面，所以答案数组就是该数字的子序列
	// 重新开始一步一步的求和
	sum = 0;
	for (int i = 0, j = 0; i < n; ++i)
	{
		sum += v[i];
		// 当我们总和大于之后，从后面开始减起，得到子序列
		while (sum > needSum)
		{
			sum -= v[j++];
		}

		// 当我们等于的时候
		if (sum == needSum)
		{
			// 这里的 tem  是维护子序列的长度
			int tem = i - j + 1;

			// 选取子序列的最大长度
			ans = (tem > ans ? tem : ans);
		}
	}

	// 输出 总长度减去符合条件的子序列最大长度，就是最小操作数
	cout << n - ans << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：