UVA-1121, Subsequence

利用了"下一個符合條件的區段一定在右邊"這個特性

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 using namespace std;

 5 int main(){

 6     int n, s;

 7     int sum[100001], tmp;

 8     int h, t, ans;

 9     sum[0]=0;

10     while(scanf("%d%d", &n, &s)!=EOF){

11         scanf("%d", sum+1);

12         for(int i=1 ; i<n ; ++i){

13             scanf("%d", &tmp);

14             sum[i+1]=sum[i]+tmp;

15         }

16         h=t=0;

17         ans=2147483647;

18         while(t<=n){

19             //cout<<h<<" "<<t<<' '<<sum[t]-sum[h]<<'\n';

20             if(sum[t]-sum[h]<s){++t;}

21             else{if(ans>(t-h)){ans=t-h;} ++h;}

22         }

23         if(ans==2147483647)ans=0;

24         printf("%d\n", ans);

25     }

26     return 0;

27 }