题目大意:给出一个序列,求出其和等于一个数的最小区间。
方法:尺取法
原理:给出一个尺子起点l和终点r,刚开始为初始值,既l=r=1;
当区间和的值小于n时,r加1,区间和继续增大,当区间和值大于n时,记录此时区间长度,更新最短有效区间长度,将l减1,区间和减小,区间长度减小。
这里我取了前缀和,来表示区间和的值。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[500010]; int b[500010]; int main() { int W; cin>>W; while(W--) { int m,n; cin>>m>>n; for(int i=1;i<=m;i++) { cin>>a[i]; b[i]=b[i-1]+a[i];//取前缀和 } int l,r; l=1,r=1; int ans=0x3f3f3f3f; while(r<=m)//边界条件 { if(b[r]-b[l-1]>=n) { ans=min(ans,(r-l+1));//逐步更新ans的值 l++; } else r++; } if(ans==0x3f3f3f3f)//当ans为被更新时,输出0 cout<<0<<endl; else cout<<ans<<endl; } }