用pre指向此时最左边暂未被保护的房子,然后利用贪心思想,遍历所有能保护pre的发射器,开启最右边的一个发射器,如果没有,则返回-1。找到最右边的发射器后,将pre更新,直到pre超过n
为什么要选满足的最右边的发射器?
因为每个发射器的保护范围是一样的,选择最右边的发射器,能最大化pre移向更右边
import java.util.Scanner;
public class Main {
static int n,r;
static int N=2010;
static int[] a=new int[N];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
r=sc.nextInt();
for (int i = 1; i <=n; i++) {
a[i]=sc.nextInt();
}
int pre=1;
int res=0;
while (pre<=n){
int t=-1;
for (int i =Math.max(1,pre-r+1); i <=Math.min(pre-1+r,n); i++) {
if (a[i]==1) t=i;
}
if (t==-1){
System.out.println(-1);
return;
}
res++;
pre=t+r;
}
System.out.println(res);
}
}