课堂复习笔记

一、贪心：把序列变成严格递增

要求只能增加数字，并且最终满足：

a[1] < a[2] < ... < a[n]

从左往右检查。若 a[i] <= a[i-1]，为了增加得最少，只把它改成 a[i-1]+1。

long long ans=0;
for(int i=2;i<=n;i++){
	if(a[i]<=a[i-1]){
		ans+=a[i-1]+1-a[i]; // 本次至少要增加的数量
		a[i]=a[i-1]+1;
	}
}

关键点：前面已经处理好的数字不要再改，每次只做当前必须做的最小修改。

二、尺取法（双指针）

尺取法用来处理“连续的一段”。用 l、r 表示当前区间 [l,r]：

• r 向右：把新元素加入区间。
• l 向右：把左端元素移出区间。
• cnt[x]：数字 x 在当前区间中出现了多少次。

推荐统一写法：

int l=1;
for(int r=1;r<=n;r++){
	// 加入 a[r]
	while(当前区间不满足要求){
		// 删除 a[l]
		l++;
	}
	// 此时 [l,r] 满足要求，可以更新答案
}

这样写不会先让 r 变成 n+1 再访问数组，也不需要单独处理第一个元素。

三、最短覆盖所有种类

目标：找最短连续区间，使它包含要求的全部种类。

用 kind 记录当前区间已有多少种不同元素。加入某个元素时，若其次数从 0 变为 1，则 kind++；删除时，若次数从 1 变为 0，则 kind--。

int l=1,kind=0,ans=1e9;
for(int r=1;r<=n;r++){
	if(cnt[a[r]]==0) kind++;
	cnt[a[r]]++;

	while(kind==m){
		ans=min(ans,r-l+1); // 当前区间已覆盖全部种类
		cnt[a[l]]--;
		if(cnt[a[l]]==0) kind--;
		l++;
	}
}

if(ans==1e9) cout<<-1;
else cout<<ans;

若题目中的种类不是固定的 1 到 m，先统计整个序列一共有多少种，再把这个数量作为 m。

若还要求区间花费最少，就在加入和删除元素时同步维护 sum：

sum+=price[a[r]]; // 加入右端卡片
sum-=price[a[l]]; // 删除左端卡片

覆盖全部种类时，用 ans=min(ans,sum) 记录最小花费。

四、最长区间：不合格元素不超过 k 个

例如：最多把 k 头黑牛变白，求最长的连续白牛段。

只要区间内黑牛数量超过 k，就不断移动左端点。

int l=1,bad=0,ans=0;
for(int r=1;r<=n;r++){
	if(a[r]==0) bad++;

	while(bad>k){
		if(a[l]==0) bad--;
		l++;
	}
	ans=max(ans,r-l+1);
}
cout<<ans;

如果输入只给出了不合格位置，可以先做标记和前缀和：

for(int i=1;i<=n;i++){
	cin>>x;
	bad[x]=1;
}
for(int i=1;i<=L;i++) sum[i]=sum[i-1]+bad[i];

// 区间 [l,r] 中的不合格位置数量
int num=sum[r]-sum[l-1];

判断答案方向：题目问“最多、最长”，使用 max；问“最少、最短”，使用 min。

五、固定长度窗口中不同数字的数量

窗口长度固定为 m。每次右端加入一个元素，若窗口过长，就删除最左边的元素。

int l=1,kind=0,ans=-1,pos=1;
for(int r=1;r<=n;r++){
	if(cnt[a[r]]==0) kind++;
	cnt[a[r]]++;

	if(r-l+1>m){
		cnt[a[l]]--;
		if(cnt[a[l]]==0) kind--;
		l++;
	}

	if(r-l+1==m&&kind>ans){
		ans=kind;
		pos=l;
	}
}
cout<<pos;

只在 kind>ans 时更新位置，自然可以保留最靠左的最优起点。

六、每种元素最多出现 k 次

加入 a[r] 后，只有 a[r] 这一种元素可能超出限制。把左端不断右移，直到它的次数重新不超过 k。

int l=1,ans=0;
for(int r=1;r<=n;r++){
	cnt[a[r]]++;
	while(cnt[a[r]]>k){
		cnt[a[l]]--;
		l++;
	}
	ans=max(ans,r-l+1);
}
cout<<ans;

七、下标和窗口检查

写完尺取法，按顺序检查：

1. 如果数组从 1 开始，输入必须写成 for(int i=1;i<=n;i++)。
2. 加入元素时，计数、种类数、区间和是否都更新了？
3. 删除元素时，这些量是否都做了相反的修改？
4. r 是否可能超过 n 后仍访问 a[r]？
5. 初始窗口为空，计数和区间和都应从 0 开始。
6. 题目求最大值还是最小值？答案初值是否正确？
7. 输出不存在时，是否严格按照题目要求输出？

一句话记忆：右端负责加入，左端负责删除，窗口状态始终要和 [l,r] 完全一致。