题解 P3662 【[USACO17FEB]Why Did the Cow Cross the Road II S】
Anguei
2019-01-29 03:46:47
考虑枚举每个长度为 $K$ 的区间端点。由于区间长度固定，所以枚举所有区间的时间复杂度为 $O(N)$（只需要移动端点位置即可）。既然枚举的区间长度已经固定为 $K$，那么区间内所有损坏信号灯都要修复。因此可以在读入损坏信号灯数据的时候预处理前缀和，在每次区间枚举过程中 $O(1)$ 查询。
已损坏的位置值为一，未损坏的值为零，那么这道题就转化为了长度固定的区间求最小和。
总时间复杂度 $O(N)$。
```cpp
// 代码里的 rep(i, a, b) 相当于 for (int i = a; i <= b; ++i)
// read() 和 println() 就是快读/快写
const int N = 100000 + 5;
int n, k, b, a[N], s[N], ans = -1u / 2; // -1u / 2 就是 int 最大值
int main() {
n = read(), k = read(), b = read();
rep(i, 1, b) a[read()] = 1;
rep(i, 1, n) s[i] = s[i - 1] + a[i];
rep(i, k, n) ans = std::min(ans, s[i] - s[i - k]);
println(ans);
}
```