奇数行从左向右读取,偶数行从右向左读取,构成长度为 K=N2 的蛇形路径。路径上相邻的格子在网格中也相邻。
将路径看成一维数组,输出逐次缩小未确定范围的冒泡排序比较序列,无需读取实际值。向右的路径边使用类型 2,向下使用类型 1,向左使用类型 4。向左时应指定左侧格子的坐标。
第一阶段用 K(K−1)/2 次操作将路径升序排列。每行已经包含该行应有的所有值,但偶数行顺序相反。再用类型 2 的冒泡排序将每个偶数行升序排列。
总操作数为
X=2N2(
输出时间为 O(N4),路径占用 O(N2) 空间。N= 时 。,检查预算的分子为 ,全部算术都在有符号 位整数范围内。
子任务 1 的朴素实现沿整条路径执行 K 轮冒泡排序,再修复偶数行。N=2,3,4 时分别使用 13,75,252 次操作,满足限制。完整范围则应跳过已经确定的后缀,将第一阶段比较数减少至 。
检查器使用 O(X) 空间存储操作。检查耗时 O(⌊108/N4⌋(N。
Solution written by GPT6