社区讨论

求看看双指针有什么问题

学术版参与者 2已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lo84mast
此快照首次捕获于
2023/10/27 12:41
2 年前
此快照最后确认于
2023/10/27 12:41
2 年前
查看原帖
题意就是在序列中找出一个最短的区间,满足区间和≥S,输出区间长度,我代码样例都挂了
CPP
#include<iostream>
#include<cstdio>
using namespace std;
int n,s;
int T;
int q[100005],a[100005];
int main()
{
	cin>>T; 
	while(T--)
	{
		for(int i=0; i<=100001; i++) q[i] = 0;
		scanf("%d%d",&n,&s);
		for(int i=1; i<=n; i++)
		{
			cin>>a[i]; q[i] = q[i-1]+a[i];
		}
		int l = 1,r = 1;
		int leng = 2e9;
		for(; r<=n; r++)
		{
			if(q[r]-q[l-1] < s) continue;
			while(q[r]-q[l-1] >= s) l++;
			leng = min(leng,r-l+1);
		}
		cout<<leng<<endl;
	}
	return 0;
}

回复

11 条回复,欢迎继续交流。

正在加载回复...