Codeforces 527D 【Clique Problem】 题解

这是一道神奇的贪心题
对于每一个点，你可以把它视为一条线段，左端点为x-w，右端点为x+w。这样对于每个abs(xi-xj)>=wi+wj，我们默认xi>=xj，那么就可以转化为xi-wi>=xj+wj，由此就可以退出由i号点构造出来的线段的左端点在由j号点构造出来的线段的右端点的右边，即这两条线段没有交点。因此这道题目就变成了：求n条线段中最多能选出多少条不相交的线段。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int l;
    int r;
}a[2000005];
bool comp(node c,node d)
{
    if(c.l<d.l)
        return 1;
    if(c.l>d.l)
        return 0;
    if(c.r<d.r)
        return 1;
    return 0;
}
int main()
{
    int n,ans=0;
    cin>>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+n+1,comp);
    for(int i=n;i>=1;--i)
    {
        int len=i;
        ans++;
        while(i-1<=n&&a[len].l<a[i-1].r)
            --i;
    } 
    cout<<ans;
    return 0;
}