bzoj 4996 [Usaco2017 Feb]Why Did the Cow Cross the Road II

bzoj 4996 [Usaco2017 Feb]Why Did the Cow Cross the Road II

​​ 题目描述

The long road through Farmer John’s farm has

N

N crosswalks across it, conveniently numbered

1 \ldots N

1…N (

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 working signals.

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

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

输入输出格式

输入格式：

The first line of input contains

N

N ,

K

K , and

B

B (

1 \leq B, K \leq N

1≤B,K≤N ). The next

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 working signals somewhere along the road.

输入输出样例

输入样例#1： 复制

10 6 5 2 10 1 5 9 输出样例#1： 复制

1 说明

感谢@ jlyzxxm1 提供题意简述

枚举每个长度为K的子串

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++; }inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;bool flag[N];int n,k,b,tmp,ans;int main(){ freopen("bzoj4996.in","r",stdin); n=read();k=read();b=read(); for (int i=1;i<=b;++i) flag[read()]=1; for (int i=1;i<=k;++i) tmp+=flag[i];ans=tmp; for (int i=k+1;i<=n;++i){ tmp-=flag[i-k];tmp+=flag[i];ans=min(ans,tmp); }printf("%d\n",ans);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。