2471: Monster06 - Silver Fox vs Monster

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：17 Solved：15

Description

Silver Fox is fighting against N monsters. The monsters are standing in a row, and we can assume them to be standing on a number line. The i-th monster, standing at the coordinate Xi, has the health of Hi. Silver Fox can use bombs to attack the monsters. Using a bomb at the coordinate x decreases the health of all monsters between the coordinates  x−D and  x+D (inclusive) by A. There is no way other than bombs to decrease the monster's health. Silver Fox wins when all the monsters' health become 0 or below. Find the minimum number of bombs needed to win.
题目的大意是：有N个怪物排成一行，你可以通过扔炸弹来攻击这些怪物，你的炸弹落下的地方，左右D距离范围内的怪物都会被扣血A，给定这些数值，同时，给出N个怪物所在的位置（X）和初始的血量H，请计算出，要消灭所有怪物，需要使用的最少的炸弹数量。

Input

Input is given from Standard Input in the following format: 
N D A  
X1 H1 
 : 
 XN HN  

Output

Print the minimum number of bombs needed to win.

Sample Input Copy 

3 3 2  
1 2  
5 4  
9 2

Sample Output Copy 

2

HINT

用贪心算法，只需要对N个怪物根据他们的位置sort一下，然后从最左边（位置最小）的那个怪物开始，先在这个怪物所在的位置X的基础上加上一个D的位置，投出刚好把这个怪物消灭的炸弹，然后找出这个炸弹攻击范围内有所有的其他怪物，将它们的血量扣减A（这时，有些怪物可能也就同时被消灭了）将着继续，从剩下的所有怪物中的最左边的怪物出发，重复上述过程，直到所有怪物都被消灭，这时统计一下炸弹的数量就可以了。（By Longqiang)

Source/Category

SubmitSubmit RecordStatisticsShowOff!