毛毛虫算法（官方称为尺取法）通常是指对数组保存一对下标（起点、终点），然后根据实际情况交替推进两个端点直到得出答案的方法，这种操作很像是毛毛虫（尺取虫）爬行的方式故得名。

Subsequence
题目描述：
给出了N个正整数（10 <N <100 000）的序列，每个正整数均小于或等于10000，并给出了一个正整数S（S <100 000 000）。 编写程序以查找序列中连续元素的子序列的最小长度，其总和大于或等于S。
输入描述：
第一行是测试用例的数量。 对于每个测试用例，程序必须从第一行读取数字N和S，并以一个间隔分隔开。 序列号在测试用例的第二行中给出，以间隔分隔。 输入将以文件结尾结束。
输出描述：
对于每种情况，程序都必须将结果打印在输出文件的单独一行上。如果没有答案，则打印0。
输入样例#:
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
输出样例#:
2
3
题目来源：
DreamJudge 1570

题目解析：这是一个典型的毛毛虫算法的应用实例，下面详细讲解一下算法过程。
我们设以as开始总和最初大于S时的连续子序列为as+...at-1，这时
as+1+...+at-2 < as+...+at-2 < S
所以从as+1开始总和最初超过S的连续子序列如果是as+1+...+at’-1的话，则必然有t<=t’。利用这一性质便可以设计出如下算法：
(1)以s = t = sum = 0初始化。
(2)只要依然有sum < S， 就不断将sum增加at，并将t增加1.
(3)如果(2)中无法满足sum >= S则终止。否则的话，更新res = min(res, t-s)。
(4)将sum减去as，s增加1然后回到(2)。

参考代码

#include<bits/stdc++.h>  
using namespace std;  
  
int a[100005];  
int main() {  
    int T, n, s;  
    scanf("%d", &T);  
    while(T--) {  
        scanf("%d%d", &n, &s);  
        for(int i = 1;i <= n;i++)  
            scanf("%d", &a[i]);  
        int l = 1,r = 1,sum = 0,ans = 0x3f3f3f3f;  
        while(1) {  
            while(sum < s && r <= n) sum += a[r++];  
            if(sum < s) break;  
            ans = min(ans, r-l);  
            sum -= a[l++];  
        }  
        if(ans == 0x3f3f3f3f) printf("0\n");  
        else printf("%d\n", ans);  
    }  
   ...

题目练习

DreamJudge 1591 逛画展