把坏灯位置转成 01 数组，在所有长度为 K 的固定窗口中用滑动窗口维护坏灯个数的最小值。
OJ: luogu
题目 ID: P3662
难度:普及-
标签:双指针模拟USACO
日期: 2026-06-18 15:06
题意
有 N 个信号灯，其中 B 个损坏。
要求最少修好多少个坏灯，才能使某一段连续长度为 K 的信号灯全部正常。
思路
先看最直接的办法：枚举每个长度为 K 的区间，重新统计这个区间里有多少个坏灯，再取最小值。
这个暴力版最符合题意：
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
int n, k, b;
int bad[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> b;
for (int i = 1; i <= b; i++) {
int x;
cin >> x;
bad[x] = 1;
}
int ans = k;
for (int l = 1; l + k - 1 <= n; l++) {
int cnt = 0;
for (int i = l; i < l + k; i++) {
cnt += bad[i];
}
ans = min(ans, cnt);
}
cout << ans << '\n';
return 0;
}但这样每个窗口都重新数一遍，复杂度是
注意这题真正要求的是：
- 找一个长度为
K的区间； - 让这个区间里的坏灯数量最少。
于是只要把坏灯位置转成 01 数组：
- 坏灯记为
1 - 好灯记为
0
题目就变成：在所有长度为 K 的固定窗口里，找窗口和最小的那个。
这正是固定长度滑动窗口模型：
- 先算第一个窗口的坏灯数
cur； - 窗口右移一格时：
- 减去离开窗口的元素；
- 加上进入窗口的元素；
- 不断更新最小值。
如果你想先补一下这个基础模型，可以参考 rbook 的《滑动窗口》： https://rbook2.roj.ac.cn/chapter3/optimization/slide-window/index.html
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
int n, k, b;
int bad[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> b;
for (int i = 1; i <= b; i++) {
int x;
cin >> x;
bad[x] = 1;
}
int cur = 0;
for (int i = 1; i <= k; i++) {
cur += bad[i];
}
int ans = cur;
for (int r = k + 1; r <= n; r++) {
cur += bad[r];
cur -= bad[r - k];
ans = min(ans, cur);
}
cout << ans << '\n';
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的难点不在数据结构，而在把题目重新表达成“固定长度窗口最小和”。
一旦完成这个转化，剩下就是最基础的滑动窗口“加新减旧”。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
