Moe's CF Life

喵~ 主人，下午好呀！今天由我，你最喜欢的小猫娘，来带你攻克一道 Codeforces 上的题目：1899E - Queue Sort。

Vlad 同学呀，他想把一个数组排好序，但是他只会一种非常奇特的排序方法，真是个笨手笨脚的人类呢，嘻嘻~ 我们就来帮帮他，看看最少需要多少次操作才能完成排序，或者干脆告诉他“不行啦，放弃吧”，喵~

题目大意

我们有一个整数数组 a，长度为 n。我们可以对它进行任意次如下操作：

取出数组的第一个元素。
把它插入到数组的末尾。
这个刚被移到末尾的元素，会和它前面的元素进行比较和交换。它会一直向左移动，直到它跑到数组的最开头，或者它 严格大于 (>) 它前面的那个元素时，才会停下来。

我们的任务就是，计算出把整个数组排成 非递减顺序 (也就是 a[i] <= a[i+1] 对所有 i 成立) 所需要的最少操作次数。如果无论如何都无法排好序，就输出 -1。

举个栗子🌰，比如数组是 [4, 3, 1, 2, 6, 4]：

我们对它进行一次操作，首先拿出队头的 4。数组暂时变成 [3, 1, 2, 6, 4]。
把 4 塞到队尾，数组变成 [3, 1, 2, 6, 4, 4]。
现在，最右边的 4 开始向左“冒泡”。
- 它和前面的 4 比较，4 并不严格大于 4，所以继续向左看。
- 它和前面的 6 比较，4 并不严格大于 6，所以交换位置，数组变成 [3, 1, 2, 4, 6, 4]。
- 现在这个 4 前面是 2。因为 4 > 2，它终于停下了脚步！
所以，一次操作后，数组 [4, 3, 1, 2, 6, 4] 就变成了 [3, 1, 2, 4, 6, 4]。

解题思路

这个问题看起来有点复杂，操作弯弯绕绕的。但是，我们可以抓住一个关键点来把它变简单，喵！

要想让整个数组排好序，那么数组里最小的那个元素，我们叫它 min_val 吧，最后肯定要跑到数组的最前面去，对不对呀？

那么，我们怎么才能让 min_val 到达数组的第一个位置呢？

假设 min_val 在数组中第一次出现的位置是 k (下标从0开始)。为了让它成为数组的第一个元素，我们必须把它前面的 k 个元素 (a[0], a[1], ..., a[k-1]) 全部通过操作移到数组的末尾去。这就像猫猫我呀，想吃到吧台最高处的猫薄荷，就得先把前面的罐头一个个推下去。推 k 个罐头，正好需要 k 次操作，喵~

当我们进行了 k 次操作后，a[k] 就顺利地成为了新的 a[0]。而它后面的那些元素 a[k+1], ..., a[n-1] 只是跟着它一起向左平移了 k 个位置，它们之间的相对顺序是完全没有改变的！

这时候，一个非常重要的结论就出现啦： 为了让最终的数组有序，从第一个 min_val 开始到数组末尾的这个子数组 a[k...n-1] 本身，必须已经是排好序的（非递减）！

为什么呢？因为在 k 次操作后，a[k] 成了队头，它是全局最小的元素。我们不能再对它进行操作了（不然它就跑到队尾去了，前功尽弃！）。既然不能动 a[k]，那它后面的 a[k+1] 等元素也相当于被“锁住”了，它们的相对位置也就固定了。如果 a[k...n-1] 这段不是有序的，比如存在 a[i] > a[i+1]（其中 i >= k），那这个逆序对就永远无法被消除了。

所以，如果 a[k...n-1] 这段不是有序的，那就直接判定为不可能，输出 -1。

那如果 a[k...n-1] 这段已经是有序的了呢？答案就是 k 次操作吗？是的喵！当 a[k...n-1] 有序时，我们进行 k 次操作。原来的 a[0]...a[k-1] 被一个个移到数组末尾。由于 a[k] 是全局最小值，而且 a[k...n-1] 是有序的，所以后面移过来的任何元素，在进行“向左冒泡”的插入操作时，都会被正确地安置在 a[n-1] 的后面。最终，整个数组就会变成有序的。

所以，我们的算法步骤就非常清晰啦：

特殊情况：先检查一下数组是不是已经有序了。如果是，那就不需要操作，答案是 0。
找到最小值：找到数组中的最小值 min_val。
找到最小值的首个位置：找到 min_val 在数组中第一次出现的位置，记为 k。
检查后缀是否有序：检查子数组 a[k], a[k+1], ..., a[n-1] 是否是升序的。
得出结论：
- 如果后缀是升序的，那么最少操作次数就是 k。
- 如果后缀不是升序的，那么就无法完成排序，答案是 -1。

题解代码

下面是 C++ 的实现代码，我已经加上了可爱的注释哦，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int min_val = 2e9; // 用一个很大的数来初始化最小值
    int min_idx = -1;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] < min_val) {
            min_val = a[i];
            min_idx = i;
        }
    }

    // 检查从第一个最小值开始的后缀是否有序
    bool possible = true;
    for (int i = min_idx; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            possible = false;
            break;
        }
    }

    if (possible) {
        cout << min_idx << '\n';
    } else {
        cout << -1 << '\n';
    }
}

int main() {
    // 这是加速输入输出的魔法咒语，让程序跑得更快，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

注：上面这段代码是我根据思路重写的，比题目提供的代码逻辑更直接一些。它在找最小元的同时记录了第一次出现的位置，然后直接检查后缀。原题解的代码思路也是完全一样的，它先用 *min_element 找值，再循环找位置，效果是相同的。

知识点介绍

这道题虽然是 E 题，但思路想通了其实并不难，它主要考察了我们的观察和逻辑推理能力。其中涉及到的知识点有：

贪心思想 (Greedy Approach) 我们的解法就是一种贪心。我们做出了一个当前看起来最好的、最直接的选择：就是想办法先把全局最小的元素 min_val 弄到队头。我们相信，如果存在解，那一定可以通过这个方式达到。在这个问题里，这个贪心策略被证明是正确的，真幸运，喵！
数组操作和性质分析 解题的关键在于分析那个奇特的操作到底对数组的结构有什么影响。我们发现，无论怎么操作，a[1...n-1] 这部分的相对顺序是保留的（只是里面的元素会被插入进来的 a[0] 打断）。通过这个性质，我们推导出了关于后缀 a[k...n-1] 的重要结论。
C++ STL min_element 在原题解代码中，使用了 *min_element(a.begin(), a.end()) 来快速找到数组中的最小值。这是 C++ 标准模板库 <algorithm> 中的一个非常好用的函数，可以帮我们省去自己写循环找最小值的麻烦。它返回一个指向最小元素的迭代器（可以看作一个指针），我们用 * 号把它解引用，就能得到最小值本尊啦，非常方便，喵~

好啦，今天的解题教室就到这里啦！希望能帮到主人哦~ 如果还有不懂的，随时可以再来问我，喵~ ❤️

题目大意 ​

解题思路 ​

题解代码 ​

知识点介绍 ​

题目大意

解题思路

题解代码

知识点介绍