202/8/4/WWX笔记(尺取法)
尺取法课堂笔记（精简版）
一、今日重点
今天主要学习了：
- 字符串贪心的两个特殊边界；
- 尺取法，也叫双指针或滑动窗口；
- 环形数组展开；
- 用计数数组维护窗口中的不同数字。
对应题目：4226、1091、4535、4872、4877、4536、4988、4878、4870。
二、字符串贪心订正
1. 魔咒升级
每次操作：
- 找到最靠前的非
z字符； - 从这里开始，一直加到下一个
z之前； - 如果已经全部是
z，立即结束。
while(k--){
int p=-1;
for(int i=0;i<s.size();i++){
if(s[i]!='z'){
p=i;
break;
}
}
if(p==-1) break;//全部是z，不能继续操作
for(int i=p;i<s.size()&&s[i]!='z';i++) s[i]++;
}
易错点：如果没有找到非 z 字符，p 还是 -1，不能访问 s[-1]。
2. 最小字典序
记录每个字母最后出现的位置时，要先初始化：
int last[26];
for(int i=0;i<26;i++) last[i]=-1;
如果无法通过交换变小：
- 有相同字符：交换两个相同字符，字符串不变；
- 所有字符都不同：交换最后两个字符。
最后两个字符的下标是：
s.size()-2
s.size()-1
s[s.size()] 已经越界。
三、尺取法是什么
尺取法用两个指针维护一段连续区间：
int l=1,r=1;
l：区间左端点；r：区间右端点；sum：当前区间[l,r]的和。
基本动作：
r向右：加入新元素，区间变大。
l向右：删除左边元素，区间变小。
数组元素都是正数时：
r右移，区间和只会变大。
l右移，区间和只会变小。
因此两个指针都只向右移动，总复杂度是 O(n)。
四、模板1：和至少为m，长度最短
对应题目：4535 最短子序列。
做法：
- 右指针加入数字；
- 当
sum>=m时，记录答案并移动左指针； - 尽量缩短区间。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,ans=1e9;
long long sum=0;
for(int r=1;r<=n;r++){
sum+=a[r];
while(sum>=m){
ans=min(ans,r-l+1);
sum-=a[l++];//继续缩短区间
}
}
if(ans==1e9) cout<<0;
else cout<<ans;
return 0;
}
本题无解输出 0。
五、模板2：和不超过m，长度最长
对应题目：
4872 松果4877 蛋糕4536 买票
做法：
- 右指针加入数字；
- 如果
sum>m，不断移动左指针； - 当前区间合法后，更新最大长度。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,ans=0;
long long sum=0;
for(int r=1;r<=n;r++){
sum+=a[r];
while(sum>m&&l<=r){
sum-=a[l++];//太重了，缩小窗口
}
ans=max(ans,r-l+1);
}
cout<<ans;
return 0;
}
一句话记忆：
太大就缩左边，合法就更新最长答案。
六、模板3：连续区间和恰好为C
对应题目：4878 求和为C。
数组元素都是正整数，所以：
sum>C：移动左指针；sum==C：答案加一；- 然后继续让右指针加入新元素。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N];
long long c;
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,cnt=0;
long long sum=0;
for(int r=1;r<=n;r++){
sum+=a[r];
while(sum>c&&l<=r) sum-=a[l++];
if(sum==c) cnt++;
}
cout<<cnt;
return 0;
}
易错点：找到 sum==c 后，循环必须继续前进，不能停在原地形成死循环。
七、模板4：包含全部m种数字的最短区间
对应题目：4870 射箭。
使用：
cnt[x]：数字x在窗口中出现了几次
have：窗口中有多少种不同数字
加入一个第一次出现的数字：
if(cnt[a[r]]==0) have++;
cnt[a[r]]++;
删除一个最后一次出现的数字：
cnt[a[l]]--;
if(cnt[a[l]]==0) have--;
完整模板：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],cnt[2010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,have=0,ans=1e9;
for(int r=1;r<=n;r++){
if(cnt[a[r]]==0) have++;
cnt[a[r]]++;
while(have==m){
ans=min(ans,r-l+1);
cnt[a[l]]--;
if(cnt[a[l]]==0) have--;
l++;
}
}
if(ans==1e9) cout<<-1;
else cout<<ans;
return 0;
}
本题无解输出 -1。
八、环形数组：回转寿司
环形数组可以复制一遍：
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
}
这样原来的环形连续区间，就变成了长度 2n 数组中的普通连续区间。
但最多只能吃原来的 n 盘，所以窗口还要满足：
r-l+1<=n
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
long long a[N],m,sum;
int n;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
a[n+i]=a[i];
}
int l=1,ans=0;
for(int r=1;r<=2*n;r++){
sum+=a[r];
while((sum>m||r-l+1>n)&&l<=r){
sum-=a[l++];
}
ans=max(ans,r-l+1);
}
cout<<ans;
return 0;
}
这套写法不需要单独判断“所有寿司能否全部吃完”，边界更简单。
九、今天的易错点
1. 0下标前缀和访问s[-1]
错误：
s[i]=s[i-1]+a[i];//i=0时会访问s[-1]
建议本章统一使用1下标，或者直接在窗口中维护 sum。
2. 循环写成l<=n、r<=n
当 r==n 后再执行 r++，可能访问 a[n+1]。
推荐使用：
for(int r=1;r<=n;r++)
3. 数组大小写成1e12
const long long N=1e12+10;//错误，数组不可能开这么大
根据题目范围开数组，例如：
const int N=2e6+10;
4. sum使用int
n 很大时，连续区间和可能超过 int，应使用：
long long sum=0;
5. 环形数组没有限制窗口长度
复制数组后，窗口不能超过原来的 n 个元素。
6. 无解输出记混
4535 最短子序列：无解输出0。
4870 射箭：无解输出-1。
7. 最小字典序交换越界
最后一个字符是 s[s.size()-1]，不存在 s[s.size()]。
8. 找到答案后指针不移动
while 循环中每一轮必须保证 l 或 r 至少有一个发生变化，否则会死循环。
十、一分钟复习
和太大：移动左指针。
需要扩大区间：移动右指针。
求最长：窗口合法时更新答案。
求最短：窗口满足条件时不断缩小。
环形数组：复制一遍，同时限制长度不超过n。
统计不同种类：使用cnt数组和have变量。
写完尺取法后检查：
1. l和r的初值对不对？
2. sum是否使用long long？
3. 每轮有没有移动指针？
4. 是否会访问数组外面？
5. 无解时应该输出什么？