题意
银狐在和怪物搏斗，怪物们站成一排，我们可以假设它们站在数轴上。第i个怪物，站在坐标Xi处，健康度为H。银狐可以用炸弹攻击怪物。在坐标x处使用炸弹会降低所有怪物在坐标x−D和x+D(包括端点)之间的生命值。除了用炸弹降低怪物的生命值外，没有其他方法。当所有怪物的治疗为0或以下时，银狐获胜。找出获胜所需的最低炸弹数量。
思路：
贪心
按怪物出现的坐标从小到大排好序，然后每次贪心的选取第i个怪物右侧距离为D处设置炸弹。这样是显然正确的。然后可以记录一下右侧xi+2D处位置，如果后面的怪物的x<=xi+2D，那么相应的生命值就减去相应的伤害。
可是如果双重循环查找会超时，那可怎么办呢？
差分
设置一个差分数组q[ ]，每次我们贪心的选取完炸弹坐标后，可以二分查找<=xi+2D范围内最远点进行差分。
AC Code
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long
const ll N = 2e5+10 ;
struct node{
ll a,b;
}res[N];
bool cmp(node A,node B){
return A.a < B.a;
}
ll q[N];
int main(){
ios::sync_with_stdio(false); cin.tie(0);
ll n,d,x;
cin >> n >> d >> x;
d <<= 1;
for(ll i = 1;i <= n; ++i){
cin >> res[i].a >> res[i].b;
}
sort(res + 1,res + n + 1,cmp);
ll sum = 0;
for(ll i = 1;i <= n;++ i){
q[i] += q[i-1];
res[i].b -= q[i] * x;
if(res[i].b <= 0) continue;
ll p = (res[i].b + x - 1) / x;
sum += p;
q[i] += p;
ll l = i,r = n;
ll temp = res[i].a + d;
while(l < r){
ll mid = l + r + 1>> 1;
if(res[mid].a <= temp) l = mid;
else r = mid - 1;
}
q[l + 1] -= p;
}
cout<<sum;
}