尺取法(双指针)
使用前缀和减少求连续区间和的复杂度
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #include <map> #include <string> #include <set> #include <stack> #include <queue> using namespace std; #define forseach(i,j,n) for(int i=j;i<n;i++) #define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout); #define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define PI acos(-1) typedef long long ll; const int maxn = 1e5+10; int ori[maxn]; int main() { //debug; ios; int T,N,S; cin>>T; while(T--) { cin>>N>>S; for(int i=1;i<=N;i++) { cin>>ori[i]; //前缀和 ori[i]+=ori[i-1]; } if(ori[N]<S) { cout<<"0"<<'\n'; continue; } int bg=1,ed=1,len=N; while(ed<=N) { int sum=ori[ed]-ori[bg-1]; //如果长度短,更新长度 if(sum>=S&&len>ed-bg+1) { len=ed-bg+1; } //和小于S ed后移 if(sum<S) ed++; //和大于s且bg在ed前 bg后移 else if(sum>=S&&bg<ed) bg++; //bg和ed在同一个位置且这个值大于S 都后移 else { bg++; ed++; } } cout<<len<<'\n'; } return 0; }