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

建筑位置:10、20、50,炸弹部署在20、50位置。
第 1 行:两个整型数值:N,M,1≤N≤1000000,表示建筑数量;0≤M≤1000000000,表示炸弹的影响范围,0 表示只能爆破炸弹所在位置(包括位置相同)的建筑。
第2行:N 个整型数值:n0,n1,...nN−1,0<ni≤1000000000,表示建筑的位置。
一个整型数值,表示最少需要的炸弹数量。
输入
6 10
0 40 5 25 10 50
输出
3
说明
至少需要3颗炸弹,可部署在 10、25、50位置上。
输入
3 10
10 20 50
输出
2
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册