「Codeforces 527D」Clique Problem

发表于 | | 阅读次数:
字数统计: 325 字

Description

题目链接：Codeforces 527D

数轴上有 $n​$ 个点，第 $i​$ 个点的坐标为 $x_i​$，权值为 $w_i​$。对于任意两个点 $i,j​$ 之间存在一条边当且仅当 $|x_i-x_j|\geqslant w_i+w_j​$。求出这张图的最大团的点数（团就是两两之间有边的顶点集合）。

数据范围：$1\le n\le 2\times 10^5$，$0\le x_i\le 10^9$，$1\le w_i\le 10^9$

Solution

我们把每个点转化成线段 $[x_i-w_i,x_i+w_i]$，我们令 $l_i=x_i-w_i$，$r_i=x_i+w_i$。那么问题就转化为：对于任意两个点 $i,j$ 之间存在一条边当且仅当 $l_i\geqslant r_j$。我们以左端点为第一关键字，右端点为第二关键字进行排序，然后直接扫一遍求解就行了。

时间复杂度：$O(n\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <cstdio>
#include <algorithm>

const int N=2e5+5;
int n,l[N],r[N],id[N];

bool cmp(int x,int y) {
    return r[x]==r[y]?l[x]<l[y]:r[x]<r[y];
}
int main() {
    scanf("%d",&n);
    for(int x,w,i=1;i<=n;++i) {
        scanf("%d%d",&x,&w);
        l[i]=x-w,r[i]=x+w,id[i]=i;
    }
    std::sort(id+1,id+n+1,cmp);
    int ans=0,las=-2e9;
    for(int i=1;i<=n;++i) if(las<=l[id[i]]) ++ans,las=r[id[i]];
    printf("%d\n",ans);
    return 0;
}
0%