先将所有建筑位置排序。
使用贪心算法:
每次从最左边还没有被爆破的建筑开始,设它的位置为 left。
为了让当前这颗炸弹覆盖尽量多的右侧建筑,炸弹必须部署在某个建筑位置上,并且要能覆盖 left,所以炸弹部署点最远可以选到 left+M。
云小核接到一个爆破任务,为了重建老旧一条街,需要将这条街上的老建筑全部爆破。云小核拿到一张图,显示了这条街上每个建筑的位置,还拿到很多炸弹,这些炸弹只能部署在建筑里,且具有一定的影响范围,距离炸弹部署点小于等于炸弹影响范围的建筑,会被一起爆破。由于预算有限,请你帮云小核计算至少需要多少炸弹,才能将所有建筑爆破。
如下图所示,至少需要 2 颗炸弹才能完成爆破任务。 炸弹影响范围:10

Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册