2021CCPC广州-C. Necklace(二分+贪心)

C. Necklace

思路：

最大最小二分，设最长长度是$len$，难点是贪心。

任选一点作为起点，每次尽量向右，一个区间要有一个特殊点。
当$len$无法满足一个区间有一个特殊点时，$len$太小一定不可行。

当一个区间可以同时覆盖至少两个特殊点时，这个区间可以左移。
左移要保证以前的区间还可以包含它的特殊点。
故开一个变量记录最长可左移距离（$maxn$），此外记录实际可移动距离($sum$)。
对于每个区间可以用其从特殊点到结尾的距离来更新$maxn$。

特殊的一点是，当区间满足可以左移时能移尽移（可以发现$maxn$是不断减小的）
此外，假设已经移动了$len$的距离，那么$maxn$ 至少要更新为 $maxn-len$ 这点需要注意。

操作完就是比较空白区域和偏移量的大小关系了。

废话：

题目数据有点水，区间问题要加1减1啥的，代码差不多都过了。

Code:

// 无
1