尺取法

尺取法通常指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法。

尺取法的实现方式是双指针。

当该区间满足一定性质时，就尝试移动左端点（起点）；如果不满足性质，就移动右端点（终点）。

模板

1
2
3
4
5
6
7
//ed为尾指针，st为头指针，sum为当前状态
while (1){
            while (ed < n && sum不满足性质 ) sum更新
            if (sum不满足性质) break;
            ans = min(ans, ed -st);
            sum -= a[st++];
        }

时间复杂度：O（n）

例题1：POJ 3061

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

题意：

给出一个序列，求一个最小区间长度，该区间需满足区间内数的和大于等于所给值。

思路：

一种可行的做法是预处理出前缀和，然后二分，时间复杂度为O(nlogn)O(nlogn)。

使用尺取法枚举所有区间，只需O(n)O(n)的时间复杂度就能求解此问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double ff;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const int N = 1e5 +7;
ll a[N];

int main () {
    int t;
    cin >>  t;
    while (t--){
        ll maxc = INF;
        int n,s;
        cin >> n >> s; 
        for (int i = 0; i < n; i ++ )cin >> a[i]; 
        ll st = 0,ed = 0;
        ll ans = INF, sum = 0;
        while (1){
            while (ed < n && sum < s) sum += a[ed++];//只要当前状态不满足题目要求，尾指针就一直右移
            if (sum < s) break;//退出条件
            ans = min(ans, ed -st);//更新答案
            sum -= a[st++];//头指针右移，尝试更新答案
        }
        if (ans == INF) ans = 0;//如果答案没有被更新过，那么答案为0
        cout << ans << endl;
    }
    return 0;
}

例题2：SDUTOJ 4843

题目链接：https://acm.sdut.edu.cn/onlinejudge3/problems/4843

题意：

本质还是求符合题意的最小区间长度。

思路：

使用map来映射

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double ff;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const int N = 1e6 +7;
int a[N];
int main () {
    int r,n,m;
    cin >> r >> n >> m;
    ff d = (ff)((ff)2*(ff)pi*(ff)r*1.0)/(ff)n*1.0;
    int s = 0;
    int ans = INF;
    map<int,int> Q,q;
    for (int i = 0; i < n; i ++ )     scanf("%d",&a[i]);
    for (int i = n; i < 2 * n; i++)     a[i] = a[i-n];//环形问题，拼接成一条链
    for (int i = 0; i < m; i ++ ) {
        int x,y;
        cin >> x >> y;
        s += y;
        Q[x] = y;//map映射
    }
    int st = 0 ,ed = 0;
    int sum = 0;
    while (1){
        while ( ed < 2*n && sum < s ) //需要注意区间最大长度为2n
            if (++q[a[ed]]  <= Q[a[ed++]]) sum++;//map映射，当前元素个数小于等于所需才会对当前状态有贡献
        if ( sum < s ) break;//退出
        ans = min(ans, ed -st);//更新答案
        if (--q[a[st]] < Q[a[st++]]) sum--;//如果删去这个元素，该元素个数就不满足条件，对当前状态的贡献为-1
    }
    ff res;
    if (ans == INF) res = 0;
    else res = (ff)(ans-1)*d;
    res += r;//加上最开始走的距离
    printf("%.5lf\n",res);
    return 0;
}

例题3：POJ 3320

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

题意：

有一本书，书上每页都有一个知识点，全书中同一知识点可能会被多次提到，题目要求通过阅读其中连续的一些页把所有知识点都覆盖。给定每页知识点，求出最小页数。

思路：

尺取

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <algorithm>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <cmath>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double ff;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const int N = 1e6 +7;
int a[N];

int main () {
    int t;
    cin >>  t;
    map<int,int> q;
    set<int> Q;
    for (int i = 0 ;  i< t; i++ ) {
        scanf("%d",&a[i]);Q.insert(a[i]);//使用set去重
    }
    int s=  Q.size();//元素
    int st = 0 ,ed = 0;
    int ans = INF, sum = 0;
    while (1){
        while (ed < t && sum < s ) if(q[a[ed++]]++ == 0) sum++;//如果这个元素没有被加入
        if (sum < s) break;//退出
        ans = min(ans , ed -st);//更新答案
        if (--q[a[st++]] == 0) sum--;//如果指针所指向的元素后，这个元素就不在区间里的话
    }
    if (ans == INF) ans = 0;
    cout << ans << endl;
    return 0;
}

例题4： POJ 2566

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