尺取法(双指针)例题。暴力算法就是两重for循环枚举i和j的位置。这里我们可以进行优化:①当i到j的和≥s时,j就不需要往后移动了;②当i变成i+1时,由于i到j-1的和小于s,i到j的和≥s,因此i+1到j-1的和一定小于s。也就是说,当i加1时,j只需后移一位即可开始新一轮的判断。
这里从i到j的和,采用前缀和实现。注意,i到j的和是j的前缀和减去i-1的前缀和。
令a[0]=0,sum[0]=0,i从1开始循环,这样a[i-1]就不会越界。
代码如下:
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[100010]; ll sum[100010];//计算前缀和 int main(){ int T; scanf("%d",&T); while(T--){ ll n,s; scanf("%lld %lld",&n,&s); memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); sum[0]=0; for(ll i=1;i<=n;i++){ scanf("%lld",&a[i]);//a从下标1开始,下标0设为0,方便后续sum[j]-sum[i] sum[i]=sum[i-1]+a[i]; } ll j=0; ll ans=100020; for(ll i=1;i<=n;i++){ while(j<=n && sum[j]-sum[i-1]<s) j++;//注意从i加到j,是j的前缀和减去i-1的前缀和 if(j>n) break; ans=min(ans,j-i+1); j--; } if(ans==100020) printf("0\n"); else printf("%d\n",ans); } return 0; }