什么是尺取法（取尺法）
其实我也不太懂到底是尺取法还是取尺法，好像都可以= =下文统一尺取法。
其实很多人写的双指针就就是尺取法，只是突然换个名字，大概的思路以及应用都是类似的。
双指针是2个指针移动，尺取法就是设定尺子的两端位置，然后移动。
简单的例子
假设给出一串01组成的字符串，要求找出连续的0或者连续的1的最长长度。
比较简单的写法就是双指针，定义两个指针，指针范围内右指针先一直右移，直到碰见不一样的字符，此时用变量记录两个指针间的距离（由于指针是一下一下移动的，所以每次变量自加1即可）。
然后左指针直接移动到右指针所在位置，然后继续重复。比较每次结束的时候的距离，更新一个最大值即可。
尺取法基本一样，这里上一下代码：
1
2
3
4
5
6
7
8
9
10
int l,r;
int ans = 0;
for(l = 0,r = 0;l < n-1;l++){
int sum = 0;
while(r+1 < n && arr[r+1] == arr[l]){
r++;
sum++;
}
ans = ans > sum ? ans : sum;
}
基本也比较简单，大概就是用l、r定义区间，先固定l为初始，然后r一直累加，直到发现不同的字符出现。然后l++，也就是左边少一位，然后r继续移动。
实际上对于这个问题而言，双指针是要优于尺取法的，因为中间连续的部分完全可以跳过。那么如果改一下问题呢？
给出一段数字，再给出一个数字k，要求子串的和大于这个k的所有子串，最短长度是多少。
那么双指针就gg了，因为左指针跳到右指针的时候就错过了很多子串的开头。
但是我们如果还是想用双指针的话，就直接变成了尺取法了。我们维护一个区间，每次右边移动一位，同时累加到sum，当sum>k的时候，就计算当前长度。
双指针仍然需要计数，但是尺取法就不用了，r-l即可得到长度。然后左边移动一位，同时减去这个sum。
就这样，当sum<=k的时候就一直右移，当sum>k的时候左移一下，然后重复。
尺取法使用的前提
上面也看到了，尺取法的使用需要一定的前提才能发挥最大的作用。第一个问题双指针就可以了，但是第二个就需要尺取法来维护一个区间。
- 能够维护一个区间，保证这个区间能够获得答案。
- 维护的具体操作可以左边移动一位、右边移动一位。
- 区间的变化是连续的而不是跳跃的。问题1就是比较跳跃的，双指针比较好，问题2不能跳跃。
- 必须符合题意：答案越小越好。
当然，4感觉不太必要，如果答案越大越好就没有意义了。
来练一个模板题吧-poj 3061
题意其实就是上面的问题2了，就不再赘述，直接上代码：
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<queue>
#include<sstream>
#include<iterator>
#include<math.h>
#include<malloc.h>
#include<string.h>
#include<stack>
#include<functional>
#define TIME std::ios::sync_with_stdio(false)
#define LL long long
#define MOD 1000000007
#define MAX 101000
#define INF 0x3f3f3f3f
using namespace std;
int T, N, S;
LL arr[MAX];
LL Min(LL a, LL b) {
return a > b ? b : a;
}
int main() {
TIME;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &S);
for (int i = 0; i < N; i++) {
scanf("%lld", &arr[i]);
}
LL ans = INF;
LL sum = arr[0];
int l = 0;
int r = 0;
if (N == 0) {
printf("1\n");
}else {
for (; l < N; l++) {
while (r + 1 < N && sum < S) {
r++;
sum += arr[r];
}
if (sum >= S) {
ans = Min(ans, r - l+1);
}
sum -= arr[l];
}
if (ans == INF) {
printf("0\n");
}else {
printf("%lld\n", ans);
}
}
}
system("pause");
return 0;
}
这个题其实有一点很蛋疼，得考虑0的情况，否则会WA的。其他还好。