题目大意:给出一个序列,求出其和等于一个数的最小区间。
方法:尺取法
原理:给出一个尺子起点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;
}
}


京公网安备 11010502036488号