Codeforces 527D(贪心+数学)

Codeforces 527D
题意：给一些点坐标$x_i$，每个点都有一个权值$w_i$，求最大的子集大小，该集合中任意两点满足$|x_i - x_j| \geq w_i + w_j$

考虑按照$x_i$升序遍历，则式子$|x_i - x_j| \geq w_i + w_j$可以拆成$x_i - x_j \geq w_i + w_j$，一样的移项，得$x_i - w_i \geq w_j + x_j$，然而做到这里我还是不会qwq。。

观察式子可以发现我们只用维护$x_i - w_i, x_i + w_i$，数形结合，$x_i - w_i, x_i + w_i$代表了一个长$2w_i$，以$x_i$为中点的线段。

然后考虑$x_i - w_i \geq w_j + x_j$和$x_j - w_j \geq w_k + x_k$，则$x_i - w_i + x_j - w_j \geq w_j + x_j + w_k + x_k$
那么$x_i-w_j \geq 2w_j+w_k+x_k$，可以得到$x_i-w_j \geq w_k+x_k$
这样说明如果$i,j$满足条件，$j,k$满足条件，则$i,k$也满足条件。

那么现在满足条件在数轴上表示为每个点代表线段不相交。那么贪心选最多不相交区间即可。

知识点：
绝对值方程可以拆，拆出来的数相同放一边，式子多数形结合，比如本题“$x_i - w_i, x_i + w_i$代表了一个长$2w_i$，以$x_i$为中点的线段。”就是一个很好的方法。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

int n;
pair<int, int > seg[200000 + 5];

bool cmp(pair<int, int > &a, pair<int, int > &b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

void clean() {
}
int solve() {
    clean();
    for (int x, w, i = 1; i <= n; i++) scanf("%d%d", &x, &w), seg[i].first = x - w, seg[i].second = x + w;
    sort(seg + 1, seg + 1 + n, cmp);
    int ans = 1, t = seg[1].second;
    for (int i = 2; i <= n; i++) {
        if (seg[i].first >= t) {
            ans++, t = seg[i].second;
        }
    }
    printf("%d\n", ans);
    return 0; 
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}