前缀和就是数组前n个数的和
因为这个题只需要求出长度没要求输出数组我们可以直接用sum数组接受数据并进行求和
首先定义l(左边指针)和r(右边指针)并初始为1;
sum【r】-sum【l】为连续子序列的和
如果有一段长度的子序列和大于s第一次找出此时r不应该向左移动 反而是l向右移动检查是否满足如果不满足r将向右移动
就这样遍历sum数组 维护mn(最小长度)
#include<iostream> #include<cstdio> #include<cstring> //尺取 typedef long long ll; using namespace std; const ll MAXN=1e5+5; const ll INF=0x3f3f3f; int main() { ll t; cin>>t; while(t--) { ll n,s,l,r; l=1;r=1; cin>>n>>s; ll sum[MAXN]; ll mn=INF; sum[0]=0; for(int i=1;i<=n;i++) { cin>>sum[i]; sum[i]+=sum[i-1]; } while(r<=n) { if(sum[r]-sum[l]<s) { r++; } else{ while(sum[r]-sum[l]>=s) { l++; mn=min(mn,r-l+1); } } } if(mn==INF) cout<<0<<endl; else cout<<mn<<endl; } return 0; }
此为本人第一次写题解(感觉挺水的) 有些东西还没讲清 敬请大佬指正