求看看双指针有什么问题
  • 板块学术版
  • 楼主i_am_a_joker
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/9/3 16:58
  • 上次更新2023/10/27 12:41:50
查看原帖
求看看双指针有什么问题
245089
i_am_a_joker楼主2022/9/3 16:58

题意就是在序列中找出一个最短的区间,满足区间和≥S,输出区间长度,我代码样例都挂了

#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;
}
2022/9/3 16:58
加载中...