题解：P8777 [蓝桥杯 2022 省 A] 扫描游戏

I_AM_CIMOTA · 2024-08-14 16:31:55 · 题解

这里给出一个 O(n\log n) 的堆做法。

首先，对所有点按照到原点的距离 d 从小到大排序，然后把所有 d\le L 的点放入一个堆中（这些点一定是排序后序列中的前 k 个）。堆的内部按照木棒还需要顺时针转多少角度才能到达这个点为关键字排序。

每次取出堆顶，显然堆顶的点就是距离木棒当前位置最近的点。我们把木棒移到这个位置，把 L 加上这个点的 z 值。既然 L 变大了，那么就会多产生一些满足 d\le L 的点（相当于是上文提到的 k 变大了），我们把这些新产生的点加入堆中。如果堆空了，那么操作结束。

不难发现，最终没进过堆的点就是碰不到的点，而每个点作为堆顶被取出的顺序就是木棒碰到这些点的顺序。

现在还有个问题，当木棒的位置变化时，堆中的排序规则也变了，怎么能保证堆中的元素是按照我们想要的顺序排序的呢？

证明：因为移动后到达的是离木棒当前位置最近的点，所以当木棒的位置移动到下一个位置时，堆中原有元素的顺序是不变的，只需要按照新规则把新元素插入堆中就是正确的了。

于是，我们发现 k 的增加相当于一个走指针的过程，走指针的同时维护了一个堆，总时间是 O(n\log n) 的。