尺取法


对于尺取法,一般用于线性表的处理。

我们有两个指针一样的东西,l和r分别指向两个元素,l于r之间的东西就是我们尝试维护的东西。

例题1

询问序列中和大于s的子串的最小长度。

题解

初始左端点为0,右端点为n-1, 长度为n-1

如果当前区间不满足,同时右移左右端点

如果当前区间满足,最小长度自减

例题2

询问序列中以第k个元素为起点的长度为n的子串的前缀和的最小值大于s的最小i

题解

设立一个前缀和最小值,以及区间和,让尺子长度逐渐增大,增大到N时结束

如果当前区间最小值满足,右移右端点,更新区间和,如果区间和小于于最小值,那么当我们右移左端点时当前最小前缀和在右端点不动时永远都是整个区间和,右移左端点直到区间和大于s,迭代

例题3

询问序列中与值t相差最小的子串和

题解

​ 对前缀和排序,再尺取

​ 如果右端点减去左端点大于t,尝试用此时的端点来更新答案,然后右移左端点,如果右端点减去左端点依旧大于t,迭代,反之先尝试更新答案,然后右移右端点直到右端点减去左端点大于t(最后一次移动前尝试更新答案),迭代

例题4

询问序列中包含所有值的最短子串

题解

​ 建立map记录有没有,cnt记录种类,以加快判断,

​ 如果当前区间不满足,右移右端点,如果此时长度大于或等于已经找到的最小长度(初始化为无穷大),右移左端点,迭代

​ 如果当前区间满足,更新最小长度,右移右端点,迭代


文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录