Mr Loser

题解 CF527D 【Clique Problem】

2019-08-12 21:04:42


数轴上有n 个点,第i 个点的坐标为xi,权值为wi。两个点i,j之间存在一条边当且仅当 abs(xi-xj)>=wi+wj。 你需要求出这张图的最大团的点数。(团就是两两之间有边的顶点集合)

什么鬼题目啊。。。看都看不懂。

别急,我们不妨把问题转换一下:

数轴上有n 个区间,每个区间的范围是[xi-wi,xi+wi]。 求这个数轴上不相交区间(公用端点不算相交)的最大数量。

好眼熟啊。。。。。。等等,这不是线段覆盖问题吗(把区间当成线段处理)?

老套路,我们把每个线段按照右端点排序,再遍历一遍就好了。

代码:

#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$ (更新成选择的线段的右端点)。

正解:


#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}$$