尺取法
青丘杨哲
·
·
个人记录
经典博客网址：
· https://blog.csdn.net/consciousman/article/details/52348439
· https://blog.csdn.net/zw1996/article/details/52089894
尺取法通常对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多。尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。
使用尺取法时应清楚以下四点：
$2$.何时推进区间的端点？
$3$.如何推进区间的端点？
$4$.何时结束区间的枚举？
尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到（根据其端点得到），那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。
典型例题 [$SCOI2009$]生日礼物
题目描述见 https://www.luogu.org/problemnew/show/P2564
【解法】
取两个下标作为左右端点，初始最左一般是$0$或$1$，然后右标向右，直至满足条件，记录这个答案，再把左标右移一位继续。大概可以想象成蚯蚓蠕动。
每次取最优解，时间复杂度$O(n)$。
【参考程序】
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
const int INF=0x7fffffff;
int N,K,T,ext[MAXN],L=1,R=0,cnt=1,ans=INF;
struct doc{
int l,r;
}num[MAXN];
bool cmp(doc a,doc b){
return a.r<b.r;
}
int main(){
scanf("%d%d",&N,&K);
for (int i=1;i<=K;i++){
scanf("%d",&T);
while (T--){
num[cnt].l=i;
scanf("%d",&num[cnt++].r);
}
}
sort(num+1,num+cnt,cmp);
for (int i=1;i<=N;i++){
ext[num[i-1].l]--;
if (ext[num[i-1].l]<=0) L--;
while (L<=K-1&&R<=N-1){
R++;
if (!ext[num[R].l]) L++;
ext[num[R].l]++;
}
int res=num[R].r-num[i].r;
if (L==K) ans=min(ans,res);
}
printf("%d",ans);
return 0;
}
```