题目描述
有 n 个房子排成一排,从左到右依次编号为 1∼n。
其中一些房子内装有无线信号发射器。
这些信号发射器的有效覆盖半径为 r。
更准确地说,如果第 p 号房子内装有信号发射器,则所有房间编号在 [p−r+1,p+r−1] 范围内的房子均可被其发出的无线信号覆盖,而其余房子则不会被其发出的无线信号覆盖。
例如,假设 n=6,r=2,且第 2、5 号房子内装有信号发射器,则第 2 号房子内的发射器发出的信号可以覆盖第 1∼3 号房子,第 5 号房子内的发射器发出的信号可以覆盖第 4∼6 号房子,将两个发射器全部打开,则无线信号可以覆盖到所有房子。
初始时,所有无线信号发射器都是关闭的,请计算至少开启多少个无线信号发射器,才能保证所有房子都被无线信号覆盖到。
大体思路
对于每个发射器,若后面的能满足前面的信号需要,则选后一个最优,由此确认思路贪心。
实现代码 $O(n)$
#include<bits/stdc++.h>
using namespace std;
int n, m, r, cnt = 1, num, ans; queue<int> v;//cnt为最左没信号的点
int main()
{
cin >> n >> r; r--;//习惯用r表示向前后各能给到多少距离的信号
for (int i = 1; i <= n; i++) { cin >> m; if (m) v.push(i); }
while (v.size())
{
num = v.front(), v.pop();//取出一个点
if (num - cnt > r) { puts("-1"); return 0; }//若信号中途中断
while (v.size() && v.front() - cnt <= r) num = v.front(), v.pop();//若后一个点更优则更新
if (cnt <= n) ans++, cnt = num + r + 1;//若信号未铺满则更新
}
if (cnt > n) printf("%d\n", ans);//信号铺满则输出
else puts("-1");
}