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; }