尺取法

尺取法

尺取法

顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。
尺取过程如下图：

伪代码部分

 int l = 0,w= 0,sum = 0,ans=n+1;
        while(1){
            while(w < n && sum<s){//从前面开始
                sum+=a[w];
                w++;
            }
            if(sum < s){//条件不满足了；
                break;  
            }
            min = w-l;
            if(min > ans)
                min = ans;
            ans = min;//ans就是最小长度
            sum -= a[l++];//尺取法的前进；
        }

练习传送门
1 【http://poj.org/problem?id=3320】
2 【http://poj.org/problem?id=2566】
3 【http://poj.org/problem?id=2100】