自动搬运

查看原文

来自洛谷，原作者为

	Anguei 俺咕诶

搬运于2025-08-24 21:51:22，当前版本为作者最后更新于2019-01-29 03:46:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑枚举每个长度为 $K$ 的区间端点。由于区间长度固定，所以枚举所有区间的时间复杂度为 $O(N)$（只需要移动端点位置即可）。既然枚举的区间长度已经固定为 $K$，那么区间内所有损坏信号灯都要修复。因此可以在读入损坏信号灯数据的时候预处理前缀和，在每次区间枚举过程中 $O(1)$ 查询。

已损坏的位置值为一，未损坏的值为零，那么这道题就转化为了长度固定的区间求最小和。

总时间复杂度 $O(N)$。

// 代码里的 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);
}