尺取法 poj3061 poj3320

尺取法就是反复推进区间的开头和结尾，来求满足条件的最下区间。

poj3061 http://poj.org/problem?id=3061

给定一个都是正整数的序列，要我们求总和不小于S的连续子序列的长度的最小值

如果序列是总和最迟大于S的连续子序列

那么

所以只有加上，从开始的连续子序列才有可能大于S

所以从开始的总和最初大于S的连续子序列是则一定有

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;
16 #define cinInt(a) scanf("%d",&a)
17 #define cinInt64(a) scanf("%I64d",&a)
18 #define cinDouble(a) scanf("%lf",&a)
19 const int INF = 1 << 30;
20 const int N = 100000 + 10;
21 int a[N];
22 void input(int &x)
23 {
24     char ch = getchar();
25     while(ch>'9' || ch<'0')
26         ch = getchar();
27     x = 0;
28     while(ch>='0' && ch<='9')
29     {
30         x = x * 10 + ch - '0';
31         ch = getchar();
32     }
33 }
34 int main()
35 {
36     int n,S,i;
37     int t;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%d%d",&n,&S);
42         for(i=0; i<n; ++i)
43         {
44             //scanf("%d",&a[i]);
45             input(a[i]);
46         }
47         int ans = INF;
48         int s = 0, t = 0,sum =0;
49         for(;;)
50         {
51             while(t<n && sum<S)
52             {
53                 sum += a[t++];
54             }
55             if(sum<S) break;
56             ans = min(ans,t-s);
57             sum -= a[s++];
58         }
59         if(ans==INF)
60             puts("0");
61         else
62             printf("%d
",ans);
63     }
64     return 0;
65 }

View Code

poj3320 http://poj.org/problem?id=3320

给我们一本p页的书，每页有一个知识点ai, 全书中同一个知识点可能会被多次提到，问我们最少读多少页连续的书。

如果区间[s,t]覆盖了所有的知识点，那么区间[s+1,t'] t'>=t , 所以可以用尺取法，即使用尺取法的条件是但区间的开头递增时，区间的结尾一定是不减的。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;
16 #define cinInt(a) scanf("%d",&a)
17 #define cinInt64(a) scanf("%I64d",&a)
18 #define cinDouble(a) scanf("%lf",&a)
19 const int INF = 1 << 30;
20 void input(int &x)
21 {
22     char ch = getchar();
23     while(ch>'9' || ch<'0')
24         ch = getchar();
25     x = 0;
26     while(ch>='0' && ch<='9')
27     {
28         x = x * 10 + ch - '0';
29         ch = getchar();
30     }
31 }
32 map<int,int> vis;
33 int a[10000000+10];
34 int main()
35 {
36     int n,i;
37     int cnt = 0;
38     while(scanf("%d",&n)!=EOF)
39     {
40         for(i=0; i<n; ++i)
41         {
42            input(a[i]);
43             if(!vis[a[i]])
44             {
45                 vis[a[i]]++;
46                 cnt++;//知识点的个数
47             }
48         }
49         vis.clear();
50         int ans = INF;
51         int s=0,t=0,cnt2=0;
52         for(;;)
53         {
54             while(t<n && cnt2<cnt)//一定要找够cnt个知识点才能够跳出循环
55             {
56                 if(vis[a[t]]==0)
57                     cnt2++;
58                 vis[a[t++]]++;
59             }
60             if(cnt2<cnt)
61                 break;
62             ans = min(ans,t-s);
63             vis[a[s]]--;
64             if(!vis[a[s++]])//因为区间的缩小，导致知识点的个数减少
65                 cnt2--;
66         }
67         printf("%d
",ans);
68     }
69     return 0;
70 }

View Code