【普及二】【长度最小的子数组】

常规
1 
#include<bits/stdc++.h>
using namespace std;
int t,n,s,a[300010],l,r,sum[300010],ans;
int main()
{
	cin>>t;
	for(int ii=1;ii<=t;ii++)
	{
		cin>>n>>s;ans=0x3f3f3f3f;
		memset(sum,0,sizeof sum);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			sum[i]=sum[i-1]+a[i];
		}
		l=0;r=0;
		while(l<=r)
		{
			while(sum[r]-sum[l-1]<s&&r<=n)
			{
				r++;
			}
			if(sum[r]-sum[l-1]>=s)
			{
				ans=min(r-l+1,ans);
			}
			l++;
		}
		if(ans==0x3f3f3f3f)
		{
			cout<<0<<endl;
		}
		else
		{
			cout<<ans<<endl;
		}
	}
	return 0;
}

WA 40

2 
#include<bits/stdc++.h>
using namespace std;
long long t,n,s,a[300005];
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(s==0){
			cout<<1<<endl;
			continue;
		}
		long long cnt=0;
		int ans=n+1;
		for(int i=1,j=1;i<=n;i++){
			while(j<=n&&cnt<s) cnt+=a[j],j++;
			if(cnt>=s) ans=min(ans,j-i);
			cnt-=a[i];
		}
		if(ans<=n) cout<<ans<<endl;
		else cout<<0<<endl;
	}
}
2 个赞
3

有思路不懂的私信我

1 个赞