POJ 3061 Subsequence 尺取

 1 //第一个答案2（5+10） 第二个 3（3+4+5）
 2 //令 sum[i]=a0+a1+...+ai,  as+...+a(t-1)>=S 
 3 //有 as+a(s+1)+...+a(t-1)=sum[t]-sum[s] 
 4 //则 ai+...+an=sum[n]-sum[i]>=S
 5 //所以问题转化成S+sum[i]在sum找 
 6 #include
 7 #include
 8 #include
 9 #include
10 #include29         {
30             scanf("%d",&a[i]);
31         }
32         
33         int sum=0,s=0,t=0;
34         int res=n;
35         while(true)
36         {
37             while(tS)
38             {
39                 sum+=a[t++];
40             }
41             if(sum//找完一圈没有就不找了 
42                 break;
43             res=min(res,t-s);
44             sum-=a[s++];
45         }
46         printf("%d\n",res);
47     } 
48     return 0;
49 }