0w1

CFR 527 D. Clique Problem ( Greedy )

Problem - D - Codeforces
題意:
給若干個點和其權重,求最多一組點,使得任意兩點距離大於等於權重和。
解法:
將點看成圓心,權重看成半徑後,問題等價選最多一組點使得圓之間無重疊。由於上下的概念無意義,可以轉化為一維的區間不覆蓋問題。給若干個區間,選最多個使得兩兩不重疊的問題。

int N;
vi X, W;

void init(){
    cin >> N;
    X = W = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> X[ i ] >> W[ i ];
}

vp pnt;

void preprocess(){
    pnt = vp( N );
    for( int i = 0; i < N; ++i )
        pnt[ i ] = pii( X[ i ] - W[ i ], X[ i ] + W[ i ] );
}

void solve(){
    sort( pnt.begin(), pnt.end(), [ & ]( const pii &a, const pii &b ){ return a.second < b.second; } );
    int ans = 0;
    for( int i = 0, lp = -INF; i < N; ++i ){
        if( lp <= pnt[ i ].first )
            ++ans,
            lp = pnt[ i ].second;
    }
    cout << ans << endl;
}