AT_abc153_f.[ABC153F] Silver Fox vs Monster

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

银狐正在与 $N$ 只怪兽战斗。

怪兽们排成一列，可以认为它们位于数轴上。第 $i$ 只怪兽位于坐标 $X_i$ ，体力为 $H_i$ 。

银狐可以使用炸弹攻击怪兽。在坐标 $x$ 处使用炸弹时，所有位于 $x-D$ 以上且 $x+D$ 以下范围内的怪兽的体力都会减少 $A$ 。除了使用炸弹，无法以其他方式减少怪兽的体力。

如果所有怪兽的体力都降为 $0$ 或以下，则银狐获胜。

请你求出银狐获胜所需使用炸弹的最小次数。

输入格式

输入以如下格式从标准输入读入。

$N$ $D$ $A$
$X_1$ $H_1$
$X_2$ $H_2$
$\vdots$
$X_N$ $H_N$

输出格式

输出银狐获胜所需使用炸弹的最小次数。

输入输出样例

输入#1
```
3 3 2
1 2
5 4
9 2
```
输出#1
```
2
```

输入#2

输出#2

输入#3

3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000

输出#3

3000000000

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$0 \leq D \leq 10^9$
$1 \leq A \leq 10^9$
$0 \leq X_i \leq 10^9$
$1 \leq H_i \leq 10^9$
$X_i$ 互不相同。
输入中的所有数值均为整数。

样例解释 1

首先在坐标 $4$ 处使用炸弹，可以使第 $1$ 只和第 $2$ 只怪兽的体力各减少 $2$ 。接着在坐标 $6$ 处使用炸弹，可以使第 $2$ 只和第 $3$ 只怪兽的体力各减少 $2$ 。通过这 $2$ 次操作，所有怪兽的体力都降为 $0$ 。无法通过 $1$ 次操作使所有怪兽的体力降为 $0$ 或以下。

样例解释 2

在坐标 $5$ 处连续使用 $5$ 次炸弹。

样例解释 3

请注意不要发生溢出。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页