题目链接

题意:给你一个长度为 len 的环,以及 n 个区间,要你选择尽量少的区间,使得它们完全覆盖整个环。问最少要多少个区间。


显然链的话每次贪心选可行的最远的即可,环的话先拆环。

现在可以预处理出每个区间选了能选到最远的区间,贪心的策略肯定还是这么选,这构成了一个树形结构。

枚举起点,向父亲倍增直到完全覆盖即可。

 


一个非常弱的准退役OIER