CF555B Case of Fugitive 题解

一道思维题。

首先我们需要转化一下题意。

对于两个相邻的区间 $[l_i,r_i],[l_{i+1},r_{i+1}]$，我们将这两个区间合并一下，得到能够连接这两个区间的线段长度：$[l_{i+1}-r_i,r_{i+1}-l_i]$。

这样，问题就变成了有若干个固定位置的点，用这些点去覆盖区间的问题。

将点按照其坐标进行排序，将这些区间按照左端点升序排序。

然后枚举每个点，对于所有左端点在这个点左边且没有使用过的区间，从中选出一条右端点最小但是大于这个点坐标的区间，用这个点覆盖这个区间。

上述过程可以使用优先队列来维护。

无解情况有哪些呢？

1. 维护的时候出现了最小右端点比这个点坐标还要小。
2. 能用的都用了，发现还有区间没有被覆盖。

这个贪心应该是一个比较常见的套路了，但是思维难度相对较高。

Code：GitHub CodeBase-of-Plozia CF555B Case of Fugitive.cpp