题解：P7195 [IOI2019] 折线

WC2025 讲，遂写题解。

考虑使用绕圈圈方法，第一步从 $(0,0)$ 走到 $x$ 最大的点，然后刚才的那条折线继续延伸直到 $y$ 最大的点的 $y$ 坐标，然后向左拐，左拐以后继续提前准备右拐。

理想情况下每个折线可以达到一个点。

刚才那个东西显然无法处理 $x_i=y_i=i$ 这样的情况。

思考一下为什么。我们从一个点绕进去了以后，到达了当前所有未遍历点的右上角。此时你无法通过延长上一条直线来节省步数。

同样的情况还有，当我们来到 $(1,1)$ 这个点时，这个点恰好是所有未遍历点的左下角。此时仍然要多花步数。

考虑单独设计一个做法求这个构造。从左下角遍历到右上角就可以了。

考虑把刚才两个东西缝起来。能绕就绕，不能绕就先把这个点删掉然后加入两个队列中的一个。

这两个队列分别是一条从左下到右上的线和从左上到右下的线。

绕完以后把这两个队列走一遍即可。精细实现可以做到步数 $\le n+3$。