题目大意
在一个数轴上有 \(n\) 个人，第 \(i\) 个人位于坐标 \(X_i\)，权值为 \(E_i\)。我们要送给一些人书，当 \(i\) 收到了一本书，那么对于所有 \(j\)，满足 \(\left | X_i-X_j \right | \le E_i-E_j\)，那么 \(j\) 会去买一本书。问最少送几个人书会使得所有人都有一本书。
思路
我们可以考虑把题目中给出的限制转化一下。
\[\begin{aligned}
\left | X_i-X_j \right | \le E_i-E_j
& \Longleftrightarrow X_i-X_j\leq E_i - E_j \land X_j - X_i \leq E_i-E_j \\
& \Longleftrightarrow E_j-X_j\leq E_i - X_i \land X_j+E_j\leq X_i+E_i
\end{aligned}
\]
那么我们考虑把每个居民转化成平面直角坐标系中的一个点。
我们用 \(E-X\) 当作横坐标，\(E+X\) 当作纵坐标，显然我们可以发现，从原点到这个居民所在点形成的矩形是该居民影响的范围。
我们还可以发现，从左到右看，选取的点的纵坐标是单调递减的，因为如果某个点右上方还有一个点，我们会直接选择那个点而放弃当前点。
按照纵坐标从上往下扫，如果一个点的横坐标大于目前扫过的最大的横坐标时，会对答案产生贡献。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 705000;
int n;
long long ans = 0;
struct Resident{
long long x,y;
}t[N];
bool cmp(Resident a,Resident b) {
if(a.y == b.y)
return a.x > b.x;
return a.y > b.y;
}
int main() {
cin >> n;
long long X,E;
for(int i = 1;i <= n; i++) {
cin >> X >> E;
t[i].x = E - X;
t[i].y = E + X;
}
sort(t + 1,t + n + 1,cmp);
long long Max = LLONG_MIN >> 4;
for(int i = 1;i <= n; i++) {
if(t[i].x > Max)
ans ++;
Max = max(Max,t[i].x);
}
cout << ans << "\n";
return 0;
}