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 N N crosswalks across it, conveniently numbered 1 … N 1 \ldots N 1…N ( 1 ≤ N ≤ 100 , 000 1 \leq N \leq 100,000 1≤N≤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 K K working signals.
共有N个信号灯,编号为1~N,有B个信号灯损坏,给你它们的编号。
问,最少修好几个信号灯,可以有K个编号连续的信号灯。
输入格式
The first line of input contains N N N, K K K, and B B B ( 1 ≤ B , K ≤ N 1 \leq B, K \leq N 1≤B,K≤N). The next B B 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 K K working signals somewhere along the road.
样例 #1
样例输入 #1
10 6 5
2
10
1
5
9
样例输出 #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;
}
文末彩蛋:
点击王老师青少年编程主页有更多精彩内容