poj 3061 尺取法或二分

经典尺取法，复杂度O(n)。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int INF = 999999;
 7 const int N = 100000;
 8 int a[N];
 9 
10 int main ()
11 {
12     int t;
13     scanf("%d", &t);
14     while ( t-- )
15     {
16         int n, s;
17         scanf("%d%d", &n, &s);
18         for ( int i = 0; i < n; i++ ) scanf("%d", a + i);
19         int p = 0, q = 0, sum = 0, len = INF;
20         while ( 1 )
21         {
22             while ( q < n && sum < s )
23             {
24                 sum += a[q++];
25             }
26             if ( sum < s ) break;
27             len = min( len, q - p );
28             sum -= a[p++];
29         }
30         if ( len == INF ) len = 0;
31         printf("%d
", len);
32     }
33     return 0;
34 }

二分也可以做，复杂度多了个log。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 const int INF = 999999;
 9 const int N = 100001;
10 ll sum[N];
11 
12 int main ()
13 {
14     int t;
15     scanf("%d", &t);
16     while ( t-- )
17     {
18         int n, s;
19         scanf("%d%d", &n, &s);
20         sum[0] = 0;
21         for ( int i = 1; i <= n; i++ )
22         {
23             scanf("%lld", sum + i);
24             sum[i] += sum[i - 1];
25         }
26         int len = INF;
27         for ( int i = n; i > 0; i-- )
28         {
29             if ( sum[i] < s ) break;
30             int pos = upper_bound( sum, sum + i, sum[i] - s ) - sum;
31             if ( pos != i )
32             {
33                 len = min( len, i - pos + 1 );
34             }
35         }
36         if ( len == INF ) len = 0;
37         printf("%d
", len);
38     }
39     return 0;
40 }