题解：P3517 [POI2011] WYK-Plot

· · 题解

看题目很容易想到跟最小圆覆盖应该会有一些关系。

然后我们结合本题单的主题是“分治与倍增”应该就很容易联想到二分去做。

也就是想办法判定有几组小于等于 mid 的半径小于等于 m 段即可。

显然随着点的增多半径不降的，所以贪心的想每段的点应该越多越好。于是可以想到暴力找每段的右端点。我们记得最小圆覆盖的复杂度是 O(n) 的，所以在暴力之后就应该是 O(n^2) 的复杂度。网上说还有对两个端点进行二分，然后看到了 O(n^2\log n) 的做法，但是我不会。

然后观察一些神秘性质，不难发现还要用到倍增，预处理出右端点的区间会在 [i+2^{k-1}-1,i+2^k-1) 这段，然后在这中间分治，就可以达到 O(n\log n) 了。

真是道卡常的好题呢!