参考博客：http://blog.chinaunix.net/uid-24922718-id-4848418.html
尺取法：返回推进区间开头和结尾，求满足条件的最小区间的方法称为尺取法。
一般可以用来解决连续的区间问题。
尺取法适用的条件： 1.连续的序列； 2.序列满足单调性。
POJ 3061
题目链接：http://poj.org/problem?id=3061
题意：给长度为n的数组和一个整数m，求总和不小于m的连续子序列的最小长度。
对于样例
10 15 5 1 3 5 10 7 4 9 2 8算法如图所示：
尺取法的4个步骤：
1.初始化左右端点 2.不断扩大右端点，直到满足条件 3.如果第二步中无法满足条件，则终止，否则更新结果 4.将左端点扩大1，然后回到第二步
复杂度为O(n)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; int a[100100]; int main() { int t; scanf("%d", &t); while(t--) { int n, s; scanf("%d %d", &n, &s); int i; for(i = 0; i < n; i++) { scanf("%d", a + i); } int sum = 0, ans = n + 1, l = 0, r = 0; //初始化ans为一个绝对大的数 for(;;) { while(r < n && sum < s) { sum += a[r++]; } if(sum < s) break; //退出循环条件 ans = min(ans, r - l); sum -= a[l++]; } if(ans > n) { ans = 0; } printf("%d\n", ans); } return 0; }
POJ 3320
题目链接：http://poj.org/problem?id=3320
题意：给一个数列，找到一个最小的区间，包含这个数列中出现的所有元素。
①不停扩展R，并把扫过知识点丢到map里，直到map的size符合要求。 ②更新结果。 ②L++，map里的对应key（a[l++]）的个数-1，相当于移出这页。 如果对应的key的个数<=0,则应该erase掉这个key，防止map::size()的误判。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> using namespace std; int a[1000100]; set<int> s; map<int, int> m; int main() { int n; scanf("%d", &n); int i; for(i = 0; i < n; i++) { scanf("%d", a + i); s.insert(a[i]); //set用来记录不同元素个数 } int tol = s.size(); //l, r分别为首尾指针 //res为最小页数，cnt为此时包含的不同元素个数 int l = 0, r = 0, res = n, cnt = 0; for(;;) { while(cnt < tol && r < n) { if(!m[a[r]]) cnt++; m[a[r]]++; r++; } if(cnt < tol) break; //不能包含所有元素，退出 res = min(res, r - l); m[a[l]]--; if(!m[a[l]]) cnt--; l++; } printf("%d\n", res); return 0; }
POJ 2566
题目链接：http://poj.org/problem?id=2566
题意：给n个数的数列和k个询问。 每个询问给出一个数t。求连续的子列和的绝对值，使其与t的最接近。输出这个连续和的绝对值，并且输出这个连续和的左端点和右端点。
感觉挺难的，看了题解后自己写的尺取法死活过不了，，很是绝望。 看了下大神的代码，也挺好理解，而且似乎比我写的还要简洁一下，真佩服。
捣鼓了许久，终于过了。
首先要计算前缀和（注意要加1个0，因为区间可能从头开始）。
然后对sum排序，因为求的是绝对值，所以排序后不会影响结果，求出的子列和也自动都是绝对值了。方便进行尺取。
然后尺取的过程就是不断找最小的差值。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef pair<int, int> P; P num[100100]; int main() { int n, k; while(~scanf("%d %d", &n, &k), n + k) { int i; num[0].first = num[0].second = 0; //加入零 for(i = 1; i <= n; i++) { scanf("%d", &num[i].first); num[i].first += num[i - 1].first; num[i].second = i; //存原始下标 } sort(num, num + n + 1); //开始的0也要参与排序，不然枚举不到所有的区间。 while(k--) { int t; int l = 0, r = 1, d = 1000000001, ans, ansl, ansr, tmp; scanf("%d", &t); //r大于n后只能l前进，此时越来越小，所以停下即可 //d为0时表示找到了与t相等的数，最优 while(r <= n && d) { tmp = num[r].first - num[l].first; if(abs(tmp - t) < d) { d = abs(tmp - t); ans = tmp; ansl = num[l].second; ansr = num[r].second; } if(tmp < t) r++; else if(tmp > t) l++; if(r == l) r++; } if(ansl > ansr) swap(ansl, ansr); printf("%d %d %d\n", ans, ansl + 1, ansr); } } return 0; }