这个题是给你一列数,让你求出其中连续和大于等于S的最小个数
思路:
有点像队列的感觉,设置一个框,不断的移动并调节框的大小。则可以做到O(N)解决
代码:
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=100011; const int inf=1<<28; int n,m,sum[maxn]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i]+=sum[i-1]; } int pre=1,ans=inf; for(int i=1;i<=n;i++) if(sum[i]-sum[pre-1]>=m) { while(sum[i]-sum[pre-1]>=m) pre++; pre--; ans=min(ans,i-pre+1); } if(ans==inf) ans=0; printf("%d\n",ans); } return 0; }