AcWing 4421. 信号---贪心---通俗易懂
原题链接
困难
#include<bits/stdc++.h>
using namespace std;
int a[1005];
int n,r;
int solve(){
int last=0,cnt=0;//last为上一个开启无线信号发射器的位置
int i=1,j=0,k=0;
while(i<=n){
j=i+r-1;k=0;//j为管理i的最右边的点,我们需要在j以内找到一个装有无线信号的发射器。
if(j>n) j=n;
while(j>last){
if(a[j]){//在j以内找到了
k=j;break;//k表示开启无线信号发射器的位置 在这个位置开启可以覆盖位置 [k-r+1,k+r-1]
}
else j--;
}
if(!k){//如果在j以内没能找到一个装有无线信号发射器,那么就无法使得所有房子都被无线信号覆盖到了,则输出 −1。
cnt=-1;
break;
}
else{
last=k;i=k+r;//更新last,i更新为当下开启无线信号发射器的位置 + 半径 位置k+r-1之前的已经被覆盖
cnt++;//数量+1
}
}
cout<<cnt<<endl;
}
int main(){
cin>>n>>r;
for(int i=1;i<=n;i++)
cin>>a[i];
solve();
return 0;
}