华为题库已更新至:华为实习&秋招真题题库，请移步。

思路

区间覆盖模板题目，这道题和区间覆盖的区别在于区间固定，我们使用贪心去解决对应的问题。

对于地址$i$，假设地址小于$i$的都已经被覆盖，那么如果我们需要覆盖它，我们可以选择的基站位置在范围$[i-R,i+R]$内。假设现在存在两个基站$x$和$y$$(y>x)$都满足对应的要求，那么我们更偏向于选择$y$基站，因为$y>x$，这样$y$的基站可以比$x$基站覆盖更多后面的地址。

因此，我们对于每一个地址$i$，我们都要进行$for~~ j = min(N, i+R)~~ to~~~ i-R+1，j-=1$的循环（这里枚举到$i-R+1$，而不枚举到$i-R$的原因在于一旦选择$i-R$这个基站，那么肯定存在大于$j$的部分实数地址无法被覆盖），从$min(N,i+R)$开始找基站，一旦找到就调用对应的基站。调用基站$j$后，那么我们范围$[j-R,j+R]$的所有地址都会被覆盖，因此，下一次我们需要枚举的地址应该从$j+R$开始（不是$j+R+1$，因为我们需要保证所有实数地址被覆盖，而不是所有整数地址被覆盖）。

类似题目推荐