尺取法 | 入门介绍篇

写在前面：

尺取法，一种神奇的技巧。在Codeforces中显示它的算法名称叫做"two pointers"， 直译成中文的话叫双指针法。

因为时间原因，下面的内容均来自于其他的博客。

---

尺取法

顾名思义，像尺子一样取一段，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。

问题分析：

eg：给定一个序列（整数），找出最短的子序列长度，使得其和大于或等于S

• 1、什么情况下能使用尺取法？
  所求解的答案在区间内连续；在通过判断之后，区间的移动有明确的方向（一般是起点到终点）

• 2、何时推进区间的端点？
  如上题：如果大于S左端点移动，如果小于S右端点移动遍历这个区间即可。

• 3、如何推进区间的端点？
  下表指针移动

• 4、何时结束区间的枚举？
  此题来说是遍历完成，也有可能是达到条件返回真即可。

例题：

总之：

区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。

【模板】

#include <iostream>
#include <cstdio>
using namespace std;
 
const int inf = 0x3f3f3f3f;
int  a[10000]; 
 
int main()
{
    int n,S;
    cin>>n>>S;
    for(int i = 0;i<n;i++)  scanf("%d", &a[i]);
    //尺取法：
    int res = inf;//答案：满足条件的最小长度
    int start=0,end=0;//左右指针
    int sum = 0;//用于与S判断的临时 和变量 
    while(1){//尺取 
        //求得一个满足条件的sum
        while(sum<S && end<n)//sum求得就跳出，下表越界就跳出
        {
            //此过程是右指针后移 
            sum += a[end];
            end++; 
        } 
        //如果是因为遍历完成(因为sum<S满足条件，只能是end<n不满足)而跳出的while，那么就不用进行下方的操作 
        if(sum<S)   break; 
        
        res = min(res,end-start);//最小区间
        
        //更新右端点 
        sum-=a[start];
        start++;  
    } 
    if(res == inf)//无解情况
        cout<<"0"<<endl;
    else
        cout<<res<<endl; 
    return 0;
}

---

写在最后：

参考资料：

• 博客：https://blog.csdn.net/f_zmmfs/article/details/81324184（文字来源）
• 博客：https://blog.csdn.net/doubleguy/article/details/81265327（图片来源）

最近腿伤了（还是关节，还好是外侧擦伤），生活、学习节奏明显放慢，做点什么都变得缓慢。这一周以来的感悟颇深，特别羡慕别人，拥有健康的双腿，能够去跑步，能够在篮球场上驰骋。希望再过几天能痊愈吧，尽快回到正常的生活节奏，也希望大家好好爱护自己的身体！

内容均摘自博客，侵删！！！