自动搬运

查看原文

来自洛谷，原作者为

	ty_mxzhn 打破天生的劣等感 || 写作悔恨的未来

搬运于2025-08-24 22:27:33，当前版本为作者最后更新于2025-01-19 15:57:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

WC2025 讲，遂写题解。

做法 1

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

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

做法 2

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

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

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

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

做法 3

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

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

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