三维爬梯游戏

对于每个终点 $i$，设 $p_i$ 为应到达该位置的起点编号（从 $0$ 开始），初始设置 $d_i=i-p_i$。将圆周展开到无限直线上，可以通过给 $d_i$ 加上 $N$ 的整数倍来表示同一终点的不同展开位置。

如果存在 $d_u-d_v>N$，就让 $d_u$ 减去 ，同时让 加上 。这一操作保持位移之和不变，也不会增加所需的交叉次数。反复执行，直到最大位移与最小位移之差不超过 。

令 $x_i=p_i+d_i$。对于 $$，这两条路径之间的最少交叉次数为

$$\left|\left\lfloor\frac{x_i-x_j-1}{N}\right\rfloor+[p_i<p_j]\right|.$$

其中 $[P]$ 在条件 $P$ 成立时为 $1$，否则为 $0$。对全部 $i<j$ 求和即可。对于负数，必须使用数学上的向下取整除法，而不能使用向零截断的整数除法。

每次选择最大和最小位移时，同一位置无需调整两次，因此调整次数为 $O(N)$。每次调整耗时 $O(N)$，枚举所有位置对耗时 $O(N^2)$。总时间复杂度为 $O(N^2)$，额外空间复杂度为 。

Solution written by GPT6