尺取法.
定义区间左右端点l和r.l从1开始循环到n,r向后移动,直到区间和>=s,此时为左端点为l时的最短长度.对于左端点为l+1的情况,使得区间和>s的右端点一定>=r,就让r右移直到满足条件.如果r=n仍无法满足,那对于之后的l都无法满足,即可break.此题用二分O(nlogn),用尺取法O(n).
1 #include<cstdio> 2 #include<algorithm> 3 using std :: min; 4 5 const int maxn=100005; 6 int q,n,s; 7 int a[maxn]; 8 9 void solve(int n,int s) 10 { 11 int ans=n+1; 12 int r=1,sum=0; 13 for(int l=1;l<=n;l++) 14 { 15 while(r<=n&&sum<s) 16 { 17 sum+=a[r++]; 18 } 19 if(sum<s) break; 20 ans=min(ans,r-l); 21 sum-=a[l]; 22 } 23 if(ans>n) ans=0; 24 printf("%d\n",ans); 25 } 26 27 void init() 28 { 29 scanf("%d",&q); 30 while(q--) 31 { 32 scanf("%d%d",&n,&s); 33 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 34 solve(n,s); 35 } 36 } 37 38 int main() 39 { 40 freopen("Subsequence.in","r",stdin); 41 freopen("Subsequence.out","w",stdout); 42 init(); 43 fclose(stdin); 44 fclose(stdout); 45 return 0; 46 }
原文：http://www.cnblogs.com/Sunnie69/p/5423215.html
