AtCoder Beginner Contest 153 花式打怪

• F 题

题目大意：
在一个2D模板游戏中，所有的怪物都是在X轴上的，每个怪物有两个属性X和HP，分别代表怪物的位置和生命值。
玩家控制的角色有一个技能，玩家每次释放技能可以选择一个位置x，技能会对[x - d, x + d]范围内的所有怪物造成a点伤害，请问，玩家最少需要使用多少次技能，才能杀死所有怪物，怪物血量清0即视为被杀死。
输入描述：
第一行包含三个正整数n，d, a， 分别表示怪物的数量和技能的范围以及单击伤害。接下来n行，每行有两个正整数x和hp分别表示一只怪物的位置和血量。

from collections import deque
from math import ceil

# n个怪物，d杀伤半径，a杀伤值
n, d, a = map(int, input().split())

ms = [map(int, input().split()) for i in range(n)]
ms = sorted([(pos, ceil(hp / a)) for pos, hp in ms])

bombs = deque()

ans = 0
valid_bomb = 0
for pos, hp in ms:
    # 查看队列里的bomb是否对当前怪物有效
    while bombs and bombs[0][0] < pos:
        bomb_border, bomb_cnt = bombs.popleft()
        valid_bomb -= bomb_cnt

    # 还需新加多少bomb才能灭掉当前怪物
    bomb_cnt = max(0, hp - valid_bomb)
    valid_bomb += bomb_cnt
    ans += bomb_cnt

    # 新加的bomb放入队列
    if bomb_cnt > 0:
        bombs.append([pos + d * 2, bomb_cnt])

print(ans)