题解报告：poj 3061 Subsequence（二分前缀法or尺取法）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=1e5+5;
 6 int t,n,S,sum,st,ed,res,a[maxn];
 7 int main(){
 8     while(~scanf("%d",&t)){
 9         while(t--){
10             scanf("%d%d",&n,&S);sum=st=ed=0;res=maxn;
11             for(int i=0;i<n;++i)scanf("%d",&a[i]);
12             while(1){
13                 while(ed<n&&sum<S)sum+=a[ed++];
14                 if(sum<S)break;//如果当前序列和小于S，直接退出
15                 res=min(res,ed-st);
16                 sum-=a[st++];//指针st往前走，减去队首值
17             }
18             if(res>n)res=0;
19             printf("%d\n",res);
20         }
21     }
22     return 0;
23 }

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<string.h>
 5 using namespace std;
 6 const int maxn=1e5+5;
 7 int t,n,S,a[maxn],sum[maxn];
 8 int main(){
 9     while(~scanf("%d",&t)){
10         while(t--){
11             scanf("%d%d",&n,&S);
12             memset(sum,0,sizeof(sum));
13             for(int i=0;i<n;++i)scanf("%d",&a[i]),sum[i+1]=sum[i]+a[i];
14             if(sum[n]<S){puts("0");continue;}//解不存在
15             int res=n;
16             for(int k=0;sum[k]+S<=sum[n];++k){
17                 int ed=lower_bound(sum+k,sum+n+1,sum[k]+S)-sum;
18                 res=min(res,ed-k);
19             }
20             printf("%d\n",res);
21         }
22     }
23     return 0;
24 }