尺取法知识点讲解

一、固定长度的情况：

最小和(sum)  

输入N个数的数列，所有相邻的M个数的和共有N-M+1个，求其中的最小值。

输入格式

第1行，2个整数N，M，范围在[3…100000]，N>M。

第2行，有N个正整数，范围在[1…1000]。 

输出格式

1个数，表示最小和。 

输入/输出例子1

输入：

6 3

10 4 1 5 5 2

输出：

10

【方法一】：枚举开始点，计算连续M个数的和，求出最小值。

程序如下：

#include
using namespace std;
long long n,m,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n-m+1;i++)
    {
        long long s=a[i];
        for(int j=i+1;j<=i+m-1;j++)
            s+=a[j];
        mins=min(s,mins);
    }
    cout<
    return 0;
}

时间复杂度是o（n*m）如果数据量太大会超时。

如图1所示，如果以第一个数开始计算也就是图1红色部分。

s1=a[1]+a[2]+a[3]   

如图2所示，如果以第二个数开始计算也就是图2蓝色部分

         s2=a[2]+a[3]+a[4]

对比图1和图2，公式s1和s2，我们会发现，如果以第一个数开始枚举m=3个数的和，和以第二个数开始枚举m个数的和，重复了a[2]+a[3]，也就是说，我们第一个数开始枚举完m个数的和后，完全不用从第二个数再重新枚举，只要在s1的基础上保留重复部分a[2]+a[3]，去掉左边的a[1]，加入右边的a[4]，让长度保持m个。

s1=a[1]+a[2]+a[3]  

s2=s1-a[1]+a[4]

尺取法：就如尺子一样，利用两个指针L和R，L代表左边枚举开始点，,R代表枚举结束点，s代表区间L到R的和，如果此时L到R刚好m个数，也就是R-L+1==m，那么找到一个长度为m的和，后面只要把s=s-a[L]+a[R+1]，L++，R++，让其长度保持为m。

【程序如下】：

#include
using namespace std;
long long n,m,s,a[100005],mins=0x7f7f7f7f7f7f7f7f;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int L=1,R=1;R<=n;R++)
    {
        s+=a[R];
        if(R-L+1==m)
        {
            mins=min(mins,s);
            s=s-a[L];
            L++;
        }
    }
    cout<
    return 0;
}

二、不固定长度情况

【程序如下】：

#include
using namespace std;
long long n,m,s,a[100005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int minL=n+1;
    for(int L=1,R=1;R<=n;R++)
    {
        s+=a[R];
        while(s>=m)
        {
            minL=min(minL,R-L+1);
            s=s-a[L];
            L++;
        }
    }
    cout<
    return 0;
}

三、总结

尺取法是一种线性算法，也是一种高效的枚举区间的方法。

记 (l,r)两个端点为一个序列内以l为起点的最短合法区间，如果r随l的增大而增大的话，我们就可以使用尺取法。

具体的做法是：

    1.初始化左右端点

    2.不断扩大右端点，直到满足条件

    3.如果第二步中无法满足条件，则终止，否则更新结果

    4.将左端点扩大1，然后回到第二步

因为r随 l增大而增大，所以 r只有 n次变化的机会，所以时间复杂度为O(n)。