题解 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)。

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