CSP/信奥赛C++刷题训练：经典前缀和例题（4）：洛谷P3662：Why Did the Cow Cross the Road II S

CSP/信奥赛C++刷题训练：经典前缀和例题（4）

[USACO17FEB] Why Did the Cow Cross the Road II S

在这里插入图片描述

题目描述

The long road through Farmer John’s farm has $N$ crosswalks across it, conveniently numbered $\ldots N$ ( $\leq N \leq 100,000$ ). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least $K$ working signals.

共有N个信号灯，编号为1~N，有B个信号灯损坏，给你它们的编号。

问，最少修好几个信号灯，可以有K个编号连续的信号灯。

输入格式

The first line of input contains $N$ , $K$ , and $B$ ( $\leq B, K \leq N$ ). The next $B$ lines each describe the ID number of a broken signal

输出格式

Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of $K$ working signals somewhere along the road.

样例 #1

样例输入 #1

样例输出 #1

使用前缀和解题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k,b,x,ans=N; 
int vis[N];//标记坏灯:1表示灯坏、0表示没坏 
int sum[N];//前缀和 
int main(){cin>>n>>k>>b;for(int i=1;i<=b;i++){cin>>x;vis[x]=1;}for(int i=1;i<=n;i++){sum[i]=sum[i-1]+vis[i];//坏灯前缀和 }for(int i=1;i<=n-k+1;i++){//枚举以i开头，长度为k的所有区间 ans=min(ans,sum[i+k-1]-sum[i-1]);}cout<<ans;return 0;
}