尺取法总结
一般地，当我们要去枚举满足条件的区间权值的区间，可以用遍历双指针 l 和 r 的做法去枚举第一个满足条件的区间，然后去维护其他数据，这样的做法就是尺取法，它的复杂度为O(n)
为什么复杂度是O(n)呢？l 只会增大，r也只会增大，因此遍历的次数加起来最多也就2*n，也是O(n)级别的复杂度
这里的权值泛指区间的属性，包括区间和，区间内数字种类数等….
尺取法需要满足的条件：区间权值大小满足区间长度的单调性，即区间长度越长，区间权值越小或越大
尺取法的优点在于：它不会去枚举到一定不满足条件的区间
它的一般格式为：
for(int l=1;l<=n;l++){while(r<n&&sum<s){r++;sum+=a[r];}if(sum>=s&&r-l+1<=n){ans=min(ans,r-l+1);}sum-=a[l];
首先，枚举 l ，就是相当于给所有状态按左端点分了个类，去枚举以 l 为起点的第一个满足条件的区间
确定为 l 后，r++就相当于剪枝了一定不满足条件的区间，在此过程中维护区间和sum
当我们发现终于枚举到第一个满足条件的区间时，去统计一下区间长度最小值
sum-=a[l]就很妙，它利用了尺取法的单调性，sum减去之后，下一轮枚举新的 l ,这样的 l，r是以新的 l 为起点的最接近满足条件的区间，这样也省得去枚举以新的 l 为起点，右端点为r之前的一定不满足条件的区间了
不光是区间和，尺取法也可以维护一些其他数据，但是这些数据必须满足关于区间长度的单调性
比如维护区间数字种类数：(145条消息) 尺取法 P1638 逛画展_lamentropetion的博客-CSDN博客
那么做题的时候怎么去考虑：
1.当要去枚举满足一定条件的区间时，可以看看需要满足的条件是否关于区间长度单调，是的话就是尺取做法没跑了
2.去整理我们要维护什么，只有满足单调性的东西我们才能放在尺取法里面维护
3.写模板，然后去维护我们想要的数据即可，一般维护数据写在r++的那个循环，还有 l 的回退，记录数据就在if那边记录就行
矫情吗；*
深藏阁楼爱情的钟
￡神魔★判官ぃ
红太狼
小灰灰
柔情只为你懂
还没有评论，来说两句吧...