Solution - CF527D Clique Problem

CF527D Clique Problem

idea:

思维

解决方案：

参考第一篇题解。

$\mid x_i - x_j\mid \geq w_i + w_j$ 感觉乱七八糟的，故先规定 $x_j > x_i$ ，然后把 $i,j$ 归类。即： $x_j - w_j\geq x_i + w_i$ 。

接下来是关键的一步：我们令 $l_i = x_i - w_i$ ， $r_i = x_i + w_i$ ，那么只要满足 $r_i\leq l_j$ 就可以连一条边 $(i,j)$ 。

我们不妨把第 $i$ 个点看成一根覆盖 $[l_i,r_i]$ 的线段，那么不相互重叠的所有线段都是一个团里面的。

这个问题就解决了。

然而对于线段覆盖这个问题，我想到的方法是先按 $l$ 排序，然后令二分优化 $dp$ ，复杂度 $O(n\log n)$ 。其实只需要按 $r$ 排序，然后贪心就好了。。。码量小常数小。（然而测试发现两种方法用时完全相同。。。）

总复杂度 $O(n\log n)$ 。