P13133 [GCJ 2018 Qualification] Trouble Sort

在 Code Jam 的秘密算法实验室里，我们花费了无数小时，致力于解决当今最复杂的问题之一：高效地将一个整数序列按非递减顺序排序。我们仔细研究了经典的冒泡排序算法，并很高兴地宣布一种新变体。 标准冒泡排序算法的基本操作是检查一对相邻的数字，如果左边的数字大于右边的数字，则交换这对数字。而我们的算法会检查一组三个相邻的数字，如果最左边的数字大于最右边的数字，就将整个三元组反转。由于我们的算法是“三元组冒泡排序”，我们将其简称为 Trouble Sort。 ``` TroubleSort(L): // L 是一个从 0 开始编号的整数列表 let done := false while not done: done = true for i := 0; i < len(L)-2; i++: if L[i] > L[i+2]: done = false reverse the sublist from L[i] to L[i+2], inclusive ``` 例如，对于 $L = 5\ 6\ 6\ 4\ 3$，Trouble Sort 的执行过程如下： - 第一轮： - 检查 $5\ 6\ 6$，无需操作：$5\ 6\ 6\ 4\ 3$ - 检查 $6\ 6\ 4$，发现 $6 > 4$，反转三元组：$5\ 4\ 6\ 6\ 3$ - 检查 $6\ 6\ 3$，发现 $6 > 3$，反转三元组：$5\ 4\ 3\ 6\ 6$ - 第二轮： - 检查 $5\ 4\ 3$，发现 $5 > 3$，反转三元组：$3\ 4\ 5\ 6\ 6$ - 检查 $4\ 5\ 6$，无需操作：$3\ 4\ 5\ 6\ 6$ - 检查 $5\ 6\ 6$，无需操作：$3\ 4\ 5\ 6\ 6$ - 第三轮检查所有三元组均无需操作，算法终止。 我们原本期待在夏威夷举办的排序特别兴趣小组会议上展示 Trouble Sort，但我们的一个实习生刚刚指出了一个问题：Trouble Sort 可能无法正确地对序列进行排序！例如，考虑序列 $8\ 9\ 7$。 我们需要你的帮助来进一步研究。给定一个长度为 $\mathbf N$ 的整数序列，判断 Trouble Sort 是否能将该序列正确地按非递减顺序排序。如果不能，请在算法结束后找出第一个排序错误的位置（从 0 开始计数）：即第一个比其后一个数大的数的下标。

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据包含两行：第一行为一个整数 $\mathbf{N}$，表示序列的长度，第二行为 $\mathbf{N}$ 个整数 $\mathbf{V}_\mathbf{i}$，表示序列中的元素。

对于每组测试数据，输出一行，格式为 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 ok（如果 Trouble Sort 能正确排序），或者为第一个排序错误的下标（从 0 开始计数），如上所述。

**样例解释** 样例 Case #1 与题目描述中的第一个例子类似。Trouble Sort 能正确排序该序列，因此输出 ok。 样例 Case #2 是题目描述中的第二个例子。Trouble Sort 无法正确排序该序列，最终结果为 $7\ 9\ 8$。$9$ 是第一个比下一个数大的数，因此第一个排序错误的下标为 $1$。 **数据范围** - $1 \leq T \leq 100$。 - 对所有 $i$，$0 \leq V_i \leq 10^9$。 **测试点 1（8 分，可见）** - $3 \leq N \leq 100$。 - 整个测试点的时间限制：10 秒。 **测试点 2（15 分，隐藏）** - $3 \leq N \leq 10^5$。 - 整个测试点的时间限制：20 秒。 **特别说明** 注意，本题的测试点 2 输入量很大，因此使用非缓冲输入可能导致读取速度较慢。此外，请注意某些编程语言默认的输入缓冲区较小。 由 ChatGPT 4.1 翻译