题目大意
数轴上有 n 个点，第 i 个点的坐标为 xi，权值为 wi。两个点 i,j 之间存在一条边当且仅当 abs(xi-xj)>=wi+wj。
你需要求出这张图的最大团的点数。（团就是两两之间有边的顶点集）
题目分析
将绝对值展开得到：
$x_i-x_j\ge w_i+w_j$或$-x_i+x_j\ge w_i+w_j$
然后就可以转成区间覆盖问题，用经典的贪心算法解决。
代码
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
39
40
41
42
43
44
45
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
struct node {
int a,b;
bool operator < (const node& x) const {
return b<x.b;
}
} a[200005];
int n,last=-0x7fffffff/2,ans=0;
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x=Get_Int(),w=Get_Int();
a[i]=(node) {x-w,x+w};
}
sort(a+1,a+n+1);
for(int i=1; i<=n; i++)
if(a[i].a>=last) {
last=a[i].b;
ans++;
}
printf("%d\n",ans);
return 0;
}
|
