洛谷 题解 P3662 【[USACO17FEB]Why Did the Cow Cross the Road II S】

一道很好的利用前缀和的题。

这道题题目描述很清楚，如果乍一看没有思路的话，我们可以考虑画图。

这是由样例画出的图。其中\(1\)表示损坏，\(0\)表示未损坏。

题目要求最少的维修量，使得有连续的\(K\)个灯。

由于区间长度被固定为\(K\)，所以我们可以考虑枚举区间，来修理区间中的灯，求出每次中的最少量即可。

如果采用朴素做法，及每次枚举区间时来计算需要修理的电灯数量，时间复杂度为\(O(NK)\)，太慢了。

让我们来考虑优化。

由于这道题涉及到区间求值，而且没有任何修改操作，所以我们很容易想到前缀和。

所以我们考虑将需要修理的位置赋为\(1\)，其余赋为\(0\)，用前缀和就能很容易的得到每个区间需要修理的电灯数了。

时间复杂度：\(O(N)\)，可过。

\(AC\) \(Code\)

#include <iostream>
#define _for(i, a, b) for (int i=(a); i<=(b); i++)
using namespace std;

const int MAXN = 100010;

int light[MAXN], s[MAXN], n, k, b, ans = 1e9;//由于求最小值，ans要赋大

int main() {
    cin >> n >> k >> b;
    _for (i, 1, b) {
        int x;
        cin >> x;
        light[x] = 1;
    } //读入+初始化
    _for (i, 1, n) s[i] = s[i-1] + light[i];//前缀和初始化
    _for (i, k, n) ans = min(ans, s[i] - s[i-k]);//统计答案。注意！i的下限为k，否则会溢出
    cout << ans << endl;//输出答案
    return 0;//完结撒花！
}

洛谷 题解 P3662 【[USACO17FEB]Why Did the Cow Cross the Road II S】

原文：https://www.cnblogs.com/zyh-cr7/p/12324207.html