poj 3061 Subsequence（尺取法）

 1 //#include <bits/stdc++.h>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 100010;
 7 int n, S, a[maxn];
 8 int solve ()
 9 {
10     int i, s, e, ans, sum;
11     ans = n + 1;
12     sum = s = i = 0;
13     while (true)
14     {
15         while (sum < S && i < n)
16             sum += a[i++];
17         if (sum < S)
18         {
19             if (ans > n)
20                 return 0;
21             return ans;
22         }
23         ans = min(ans, i-s);
24         sum -= a[s];
25         s ++;
26     }
27 }
28 int main ()
29 {
30     int t;
31     scanf ("%d", &t);
32     while (t --)
33     {
34         scanf ("%d %d", &n, &S);
35         for (int i=0; i<n; i++)
36             scanf ("%d", &a[i]);
37         int res = solve();
38         printf ("%d\n", res);
39     }
40     return 0;
41 }