本文主要是介绍尺取法专题 POJ 3061 POJ 3320 POJ 2566，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考博客：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;
}这篇关于尺取法专题 POJ 3061 POJ 3320 POJ 2566的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
