模拟
思路大概就是,把所有的信号发射器打开,看看那些地方有信号,然后再尝试去掉某些信号发射器,如果可以则记录能够去掉发射器的个数
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, r;
int a[N];
int st[N];
int main(){
cin >> n >> r;
int cnt = 0;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
if(a[i] == 1){//这里把所有的信号器打开
cnt ++;
for(int j = i - r + 1; j <= i + r - 1; j ++){
if(j < 1 || j > n) continue;
st[j] ++;
}
}
}
for(int i = 1; i <= n; i ++){//如果所有的信号打开了,依然有地方没有信号,那么有房子没有覆盖到信号
if(st[i] == 0){
cout << "-1";
return 0;
}
}
int res = 0;
for(int i = 1; i <= n; i ++){
if(a[i] == 1){//尝试去掉第i个灯
int flag = true;
for(int j = i - r + 1; j <= i + r - 1; j ++){
if(j < 1 || j > n) continue;
st[j] --;
if(!st[j]) flag = false; //如果去掉了第i个信号发射器依然没有信号变成0,说明这个信号器发射器是可以去掉的
}
if(!flag){//如果不能去掉则要把去掉的信号加回来
for(int j = i - r + 1; j <= i + r - 1; j ++) st[j]++;
}else res ++; //如果可以去掉则记录去掉的信号发射器数量
}
}
cout << cnt - res << endl; //最后减去可以去掉的信号发射器
return 0;
}
鉴于算法基础课区间覆盖的补充(贪心 + 双指针)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, r;
struct Range{
int l, r;
bool operator < (const Range &w) const{
return l < w.l;
}
}range[N];
int main(){
cin >> n >> r;
int st = 1, ed = n, idx = 0;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
if(x) range[idx++] = {i - r + 1, i + r - 1};
}
sort(range, range + idx);
int res = 0;
bool success = false;
for(int i = 0; i < n; i ++){
int j = i, r = -2e9;
while(j < n && range[j].l <= st){//遍历所有左端点在start的左边的所有区间里面,右端点的最大值
r = max(r, range[j].r);
j ++;
}
if(r < st) break; //如果找到的最大值比左端点都还要小,那么肯定不存在
res ++;//否则加入答案
if(r >= ed) {//如果最大值大于了ed那么就找到了;
success = true;
break;
}
st = r + 1;//更新st
i = j - 1;
}
if(!success) res = -1;
cout << res;
return 0;
}