NC24076. [USACO 2017 Feb S]Why Did the Cow Cross the Road II
描述
输入描述
The first line of input contains N, K, and B (1≤B,K≤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
输入:
10 6 5 2 10 1 5 9
输出:
1
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 1248K, 提交时间: 2020-03-14 17:47:20
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n,k,b;
int ans=0x7f7f7f7f;
int vis[MAXN],sum[MAXN];
int main()
{
scanf("%d%d%d",&n,&k,&b);
for(int i=1;i<=b;i++)
{
int x;
scanf("%d",&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++)
ans=min(ans,sum[i+k-1]-sum[i-1]);
printf("%d",ans);
}