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$为中点的线段。”就是一个很好的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}
------ 本文结束 ------