2021CCPC广州-C. Necklace(二分+贪心)
C. Necklace
思路：
最大最小二分，设最长长度是 l e n len len，难点是贪心。
任选一点作为起点，每次尽量向右，一个区间要有一个特殊点。
当 l e n len len无法满足一个区间有一个特殊点时， l e n len len太小一定不可行。
当一个区间可以同时覆盖至少两个特殊点时，这个区间可以左移。
左移要保证以前的区间还可以包含它的特殊点。
故开一个变量记录最长可左移距离（ m a x n maxn maxn），此外记录实际可移动距离( s u m sum sum)。
对于每个区间可以用其从特殊点到结尾的距离来更新 m a x n maxn maxn。
特殊的一点是，当区间满足可以左移时能移尽移（可以发现 m a x n maxn maxn是不断减小的）
此外，假设已经移动了 l e n len len的距离，那么 m a x n maxn maxn 至少要更新为 m a x n − l e n maxn-len maxn−len 这点需要注意。
操作完就是比较空白区域和偏移量的大小关系了。
废话：
题目数据有点水，区间问题要加1减1啥的，代码差不多都过了。
Code:
// 无
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！