[POJ3061]Subsequence

题目链接：http://poj.org/problem?id=3061

马概上学了一下《挑战程序竞赛》中作为尺取法，本题是尺取法的一道很典型的例题。尺取法真是一个很不错的小技巧。它的重点在于线性地解决了求出了满足条件的最小区间。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 inline int min(int a, int b) {
23     return a < b ? a : b;
24 }
25 
26 const int maxn = 100010;
27 int n, s;
28 int num[maxn];
29 
30 int solve() {
31     int ans = n + 1; //记录长度
32     int ll = 0;      //数据左端
33     int rr = 0;      //数据右端
34     int sum = 0;     //记下和
35     while(1) {
36         while(sum < s && rr < n) { //求sum，到恰好大于s为止。或者右端突破数据范围
37             sum += num[rr++];
38         }
39         if(rr >= n) {   //如果是因为右端突破了数据范围而出循环，那么出总循环
40             break;
41         }
42         ans = min(ans, rr - ll);    //统计区间的最小长度
43         sum -= num[ll++];           //减掉左边的头部的数据
44     }
45     return ans > n ? 0 : ans;       //ans>n的话，则说明超出数据范围。不满足
46 }
47 
48 int main() {
49     // freopen("in", "r", stdin);
50     int T;
51     scanf("%d", &T);
52     while(T--) {
53         scanf("%d %d", &n, &s);
54         for(int i = 0; i < n; i++) {
55             scanf("%d", &num[i]);
56         }
57         printf("%d
", solve());
58     }
59 }

同理还有POJ3320

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 inline int min(int a, int b) {
23     return a < b ? a : b;
24 }
25 
26 const int maxn = 100010;
27 int n, s;
28 int num[maxn];
29 set<int> var;
30 
31 int solve() {
32     int ans = n;
33     int ll = 0;
34     int rr = 0;
35     int cnt = 0;
36     map<int, int> show;
37     while(1) {
38         while(rr < n && cnt < var.size()) {
39             if(show[num[rr++]]++ == 0) {
40                 cnt++;
41             }
42         }
43         if(cnt < var.size()) {
44             break;
45         }
46         ans = min(ans, rr - ll);
47         if(--show[num[ll++]] == 0) {
48             cnt--;
49         }
50     }
51     return ans;
52 }
53 
54 int main() {
55     // freopen("in", "r", stdin);
56     while(~scanf("%d", &n)) {
57         var.clear();
58         for(int i = 0; i < n; i++) {
59             scanf("%d", &num[i]);
60             var.insert(num[i]);
61         }
62         printf("%d
", solve());
63     }
64 }