题解 CF527D 【Clique Problem】
t162
2019-08-12 21:04:42
>数轴上有n 个点，第i 个点的坐标为xi，权值为wi。两个点i,j之间存在一条边当且仅当 abs(xi-xj)>=wi+wj。 你需要求出这张图的最大团的点数。（团就是两两之间有边的顶点集合）
什么鬼题目啊。。。看都看不懂。
别急，我们不妨把问题转换一下：
>数轴上有n 个区间，每个区间的范围是[xi-wi,xi+wi]。 求这个数轴上不相交区间（公用端点不算相交）的最大数量。
好眼熟啊。。。。。。等等，这不是线段覆盖问题吗（把区间当成线段处理）？
老套路，我们把每个线段按照右端点排序，再遍历一遍就好了。
代码：
```cpp
#include<bits/stdc++.h> //终于懒了一回
using namespace std;
struct point{
int l,r;
friend inline bool operator < (point x,point y){
return x.r<y.r;
}
}a[200001];
int n,ans=1;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,w;
scanf("%d%d",&x,&w);
a[i].l=x-w;
a[i].r=x+w;
}
sort(a+1,a+1+n);
for(int i=2;i<=n;i++){
if(a[i].l>=a[i-1].r)ans++;
}
printf("%d\n",ans);
return 0;
}
```
交上去一看，WA！我们分析一下原因。明白了，上面代码的第二个循环的判断出了问题。拿一个例子：
```
----- -----
------------
```
本来应该选择上面两条线段的，但是结果却是`1`。为什么呢？因为我们在判断的时候是和前一条线段的右端点进行比较的，正确的应该是和已经选择的最右边线段的右端点进行判断。我们开一个变量$R$，它的初值是（排序后）第一条线段的右端点。后面如果选择了一个线段，那么就更新$R$（更新成选择的线段的右端点）。
正解：
```cpp
#include<bits/stdc++.h> //终于懒了一回
using namespace std;
struct point{
int l,r;
friend inline bool operator < (point x,point y){
return x.r<y.r;
}
}a[200001];
int n,ans=1,r; //这里的r就是描述中的R
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,w;
scanf("%d%d",&x,&w);
a[i].l=x-w;
a[i].r=x+w;
}
sort(a+1,a+1+n);
r=a[1].r; //给R赋初值
for(int i=2;i<=n;i++){
if(a[i].l>=r){
r=a[i].r; //更新R
ans++;
}
}
printf("%d\n",ans);
return 0;
}
```
[$$\textbf{Blog}$$](https://bambusoideae.cn/)