poj 3061 Subsequence（尺取法）

题目连接：

题目大意：

　　一个有n个数的序列和一个整数s，找出一个最短序列，最短序列中各个数相加的和大于等于s。

解题思路：

　　题目比较简单，写博记录一下思想——尺取法，用其他方法也可以解决。

 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
", res);
39     }
40     return 0;
41 }

本文为博主原创文章，未经博主允许不得转载。