题解 P5552 【Chino的试卷】

· · 题解

比赛结束这么久一直忘了把官方题解放上来

题目归纳为，给定一个循环队列，每次比较队头的两个元素 p1,p2，距离当前指针的位置，如果 p1 不比 p2 远，令指针指向 p1, 并弹出队列，否则将 p1 放回队尾 统计指针移动距离

模拟可以获得30分

因为每个元素只会出队一次，所以我们考虑优化寻找下一个出队元素的过程

考虑二分，但是这没有单调性啊，比如我可能在第 i 个位置停下，却不一定 能在第 i + 1 个位置停下啊。 换一种判断方式，如果我们会在区间 [1, i] 中的某个位置停下， 就一定会在区间 [1, i + 1] 的某个位置停下 所以如何判断对于当前指针 s，我们是否会在区间 [1, i] 停下呢？

我们可以发现，对于相邻的两个元素 pi, pi+1，是可以找到一条，分界线的，其中分界线的一侧都会被拦下来，而另一侧都可以通过

我可以维护区间中分界线的交集！线段树即可

所以思路就是先二分，然后判断区间的交集是否能拦下从 s 处出发的老师

最终复杂度O(nlog^2n)

如果写了正解还是 TLE 可能只是常数过大(，std 没有加快读仍然只在 2s 内完成了