Moe's CF Life

喵~ 各位热爱算法的伙伴们，大家好呀！我是你们的小助教猫娘，今天也要元气满满地解决一道有趣的题目哦！这次我们要挑战的是 Codeforces 上的 F2. Flying Sort (Hard Version)，一个需要动点小脑筋的排序问题，一起来看看吧，喵！

题目大意

我们拿到一个数组 a，里面可能有重复的数字哦。我们可以对这个数组做两种操作：

把任意位置的元素 a[i] 抓到数组的最前面。
把任意位置的元素 a[i] 甩到数组的最后面。

我们的任务是，用最少的操作次数，让整个数组变成非递减的有序状态（也就是 a[1] <= a[2] <= ... <= a[n]）。就像猫娘把散落一地的毛线球按大小排好一样，要用最少的动作完成！

举个例子：a = [4, 7, 2, 2, 9]。我们可以把第一个 2 移到最前，数组变成 [2, 4, 7, 2, 9]。再把第二个 2 移到最前，数组变成 [2, 2, 4, 7, 9]。这样就排好序啦，总共移动了 2 次。我们的目标就是找到这个最小的移动次数。

题解方法

直接思考“最少移动多少个”有点复杂，不如换个思路想想，喵？我们可以反过来问：“最多可以有多少个元素不需要移动？”

如果我们决定保留数组中的一个子序列，让它们原地不动，那么所有其他的元素都必须被移动。为了让最终的数组有序，我们保留的这个子序列本身，必须是最终排好序的数组中的一个连续部分。

比如说，如果数组 a 排序后应该是 [2, 2, 3, 4, 4, 5]，那么我们可以保留的子序列可以是 [3, 4, 4]，但不能是 [2, 2, 5]。因为 2 和 5 中间隔着 3 和 4，如果我们只留下 2 和 5，那么 3 和 4 就得被移走，它们就没地方待了呀！

所以，问题就转化成了：在原数组 a 中，找到一个最长的子序列，这个子序列的元素值，在所有不重复的元素值排序后，是连续的。

这个我们要保留的子序列，它的结构会是这样的： (数值 d_i 的一个后缀) + (数值 d_{i+1} 的全部) + ... + (数值 d_{j-1} 的全部) + (数值 d_j 的一个前缀) 并且，这些元素在原数组中的相对位置（也就是下标）必须是严格递增的。

为了找到这个最长的“不动”子序列，我们可以用一种类似动态规划的思路来解决。我们会遍历所有不重复的数值 d_0, d_1, ...，尝试构建出最长的可以保留的链条。

我们的算法会这样做：

首先，对原数组进行离散化，得到所有不重复的元素值，并记录每个值在原数组中出现的所有位置。
然后，我们从第一个不重复值 d_0 开始，一步步向后构建最长的“不动”子序列。我们会维护一个当前链的长度 curlen。
在处理 d_i 时，如果它的所有出现位置都在 d_{i-1} 的后面，那太棒了，我们可以直接把 d_i 的所有元素都接在链上！
如果不行，说明链条断了。这时我们有两种选择：
- 将当前链条（截止到 d_{i-1}）和 d_i 的一个后缀（位置在链条末尾之后的那些）连接起来。
- 或者，开启一个新链条，这个新链条可以由 d_{i-1} 的一个前缀（位置在 d_i 第一个元素之前）和 d_i 的全部元素组成。
除了上面这些情况，还有一个特殊但很重要的组合：只由 d_i 的一个前缀和 d_{i+1} 的一个后缀组成的子序列。这个也需要单独计算。
在所有这些可能中取一个最大长度 mxlen。

最后，总元素数 n 减去我们能保留的最大长度 mxlen，就是最少的移动次数啦！是不是很简单呢？喵~

题解代码解析

下面我们来一步步解析这份可爱的 C++ 代码吧！

cpp

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

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::vector<int> d; // 用于离散化
    d.reserve(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        d.push_back(a[i]);
    }

    if (n <= 1) {
        std::cout << 0 << std::endl;
        return;
    }

    // 1. 离散化和位置记录
    std::sort(d.begin(), d.end());
    d.erase(std::unique(d.begin(), d.end()), d.end());

    int m = d.size();
    std::vector<std::vector<int>> pos(m);
    for (int i = 0; i < n; ++i) {
        // 将原数值映射到 0, 1, ..., m-1
        int compressed_val = std::lower_bound(d.begin(), d.end(), a[i]) - d.begin();
        pos[compressed_val].push_back(i);
    }

    int mxlen = 0;
    int curlen = 0;
    int r = -1; // 记录前一个值在链中最后出现的位置

    // 2. 主循环，构建链条
    for (int i = 0; i < m; ++i) {
        if (i > 0 && pos[i].front() > r) {
            // Case A: 链条可以完美延伸
            curlen += pos[i].size();
        } else {
            if (i > 0) {
                // Case B: 链条断裂，尝试连接 (旧链 + d_i的后缀)
                auto it = std::upper_bound(pos[i].begin(), pos[i].end(), r);
                mxlen = std::max(mxlen, curlen + (int)(pos[i].end() - it));
            }
            // Case C: 开启新链，可以是 (d_{i-1}的前缀 + d_i的全部)
            if (i > 0) {
                auto it = std::lower_bound(pos[i-1].begin(), pos[i-1].end(), pos[i].front());
                curlen = (int)(it - pos[i-1].begin()) + pos[i].size();
            } else { // i == 0，链条从第一个值开始
                curlen = pos[i].size();
            }
        }
        mxlen = std::max(mxlen, curlen);
        r = pos[i].back();
    }

    // 3. 特殊情况：(d_i 的前缀) + (d_{i+1} 的后缀)
    for (int i = 0; i < m - 1; ++i) {
        for (size_t j = 0; j < pos[i].size(); ++j) {
            // 找到 d_{i+1} 中第一个位置 > pos[i][j] 的元素
            auto it = std::upper_bound(pos[i+1].begin(), pos[i+1].end(), pos[i][j]);
            int current_prefix_len = j + 1; // d_i 前缀长度
            int next_suffix_len = pos[i+1].end() - it; // d_{i+1} 后缀长度
            mxlen = std::max(mxlen, current_prefix_len + next_suffix_len);
        }
    }
    
    // 4. 单独一个值的最长子序列
    for(int i=0; i<m; ++i) {
        mxlen = std::max(mxlen, (int)pos[i].size());
    }

    std::cout << n - mxlen << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

代码讲解喵~

第 1 部分：预处理
- 我们先读入数据，然后用 d 数组来做离散化。sort 和 unique 之后，d 就保存了所有不重复的元素，并且是排好序的。
- pos 是一个二维向量，pos[k] 存储了离散化后值为 k 的所有元素在原数组 a 中的下标。因为我们是按顺序遍历 a 来填充的，所以 pos[k] 里的下标自然就是有序的啦。
第 2 部分：主循环
- 这是算法的核心！我们遍历所有不重复值 d_i ( i 从 0 到 m-1)。
- curlen 记录当前正在构建的链的长度，r 记录链中上一个值的最后一个元素的下标。
- if (pos[i].front() > r): 这是最理想的情况。当前值 d_i 的第一个元素位置，都比链中上一个值 d_{i-1} 的最后一个元素位置 r 要大。这意味着我们可以把 d_i 的所有小伙伴都加入链中，所以 curlen 增加 pos[i].size()。
- else: 链条断了，喵！d_i 的第一个元素插队到了 d_{i-1} 的前面。
  - Case B: 我们不能把整个 d_i 都接上，但可以试试接上一部分。我们可以保留到 d_{i-1} 为止的链（长度 curlen），然后从 d_i 中挑选出所有位置在 r 之后的元素（一个后缀）。用 upper_bound 可以高效地计算出这个后缀的长度。
  - Case C: 既然旧链不好接，我们可以开启一个新链！这个新链可以由 d_i 的全部元素，加上 d_{i-1} 中所有位置在 d_i 第一个元素之前的那部分（一个前缀）组成。用 lower_bound 可以算出这个前缀的长度。curlen 被更新为这个新链的长度。
- 每次循环的最后，我们都会用 curlen 更新 mxlen，并把 r 更新为当前值 d_i 的最后一个元素的位置 pos[i].back()。
第 3 和 4 部分：查漏补缺
- 主循环考虑了大部分情况，但有一种 (d_i 的前缀) + (d_{i+1} 的后缀) 的组合可能被漏掉。所以需要一个额外的循环来专门处理这种情况。它遍历所有相邻的值对 (d_i, d_{i+1})，再遍历 d_i 的所有可能的前缀，计算出能接上的最长 d_{i+1} 后缀，然后更新 mxlen。
- 最后，也要考虑最简单的情况：只保留一种数值的元素。它的长度就是这个数值出现的次数。

最后，n - mxlen 就是我们要的答案啦！Purrfect!

题目大意 ​

题解方法 ​

题解代码解析 ​

相关知识点介绍 ​

题目大意

题解方法

题解代码解析

相关知识点介绍