F1. Flying Sort (Easy Version) - 题解

比赛与标签

比赛: Codeforces Round 650 (Div. 3) 标签: dp, greedy, two pointers 难度: *2100

喵喵，这是什么任务呀？

主人你好呀~！这次的任务是酱紫的：我们拿到一个由 n 个各不相同的数字组成的数组 a，喵~。我们可以对它做两种操作：

把任意一个元素 a[i] 抓到数组的最前面。
把任意一个元素 a[i] 丢到数组的最后面。

我们的目标，就是用最少的操作次数，让整个数组变得从小到大整整齐齐的（也就是非递减排序啦）。

比如说，数组是 [4, 7, 2, 3, 9]，最后要变成 [2, 3, 4, 7, 9]。我们需要找到最省力气的办法哦！

寻找不动的小鱼干喵~

要让操作次数最少，我们不妨反过来想一想，哪些元素可以像乖巧的小鱼干一样，待在原地不动呢？喵~

如果我们决定保留一部分元素不动，那么剩下的元素就必须全部移走。所以，最少化移动的元素数量，就等价于最大化保留的元素数量！

那么，什么样的元素可以被保留下来呢？

它们在原数组中的相对顺序不能改变。比如原数组里 x 在 y 前面，那我们保留它们之后，x 还是得在 y 前面。这不就是子序列的定义嘛！
这些被保留的元素，在最终排好序的数组里，必须是连续的一段！为什么呢？因为我们只能把元素移动到最前或最后。比如最终排好序是 [1, 2, 3, 4, 5]，如果我们保留 [2, 4]，那 3 怎么办呢？我们没法把它插到 2 和 4 中间呀。但如果我们保留 [2, 3, 4]，那就可以把 1 移到最前面，把 5 移到最后面，完美达成目标！

所以，我们的问题就转化成了一个更清晰的目标： 找到原数组 a 的一个最长的子序列，这个子序列同时也是 a 排序后数组的一个连续子数组。

这个最长子序列的长度就是我们能保留的元素数量，记作 max_len。那么，需要移动的元素数量就是 n - max_len 啦！

为了方便处理，我们可以引入“排名”的概念。先把原数组 a 里的所有数排个序，得到 b_1, b_2, ..., b_n。如果一个数 x 是排序后第 k 小的数，我们就说它的排名是 k。

现在，问题就变成了： 在原数组中，找到一个最长的子序列，它们的排名正好是连续的 k, k+1, k+2, ...。

举个例子：a = [4, 7, 2, 3, 9]

排序后是 [2, 3, 4, 7, 9]。
我们给每个数标上排名：2(rank 1), 3(rank 2), 4(rank 3), 7(rank 4), 9(rank 5)。
原数组用排名表示就是 p = [3, 4, 1, 2, 5]。（因为 a[0]=4 是第3小的，a[1]=7 是第4小的，以此类推）
现在我们在 p 中寻找形如 [k, k+1, ...] 的最长子序列。
- [3, 4] 是一个，p 中 3 在 4 前面。
- [1, 2] 是一个，p 中 1 在 2 前面。
- [4, 5] 是一个，p 中 4 在 5 前面。
- 咦，我们发现 [3, 4, 5] 也是一个子序列！在 p 中它们分别在第0、1、4个位置，顺序是对的！p = [**3**, **4**, 1, 2, **5**]。它的长度是3。
最长的这种子序列长度是3，所以 max_len = 3。答案就是 n - max_len = 5 - 3 = 2 次移动。和样例一样耶！

要怎么高效地找到这个最长子序列呢？我们可以用一个简单的动态规划（DP）哦！设 dp[k] 表示我们目前找到的、以排名 k 结尾的、排名连续的子序列的最大长度。

当我们遍历原数组（的排名形式 p），遇到一个排名为 rank 的元素时，它有可能接在一个以 rank-1 结尾的序列后面，形成一个更长的序列。所以状态转移就是： dp[rank] = dp[rank - 1] + 1

我们从头到尾扫一遍排名数组 p，不断更新 dp 表，并记录下 dp 值中出现过的最大值，这个最大值就是我们想要的 max_len 啦！

让代码动起来喵！

下面就是把思路变成代码的时刻啦，主人请看~

cpp

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

void solve() {
    int n;
    std::cin >> n;
    // 用一个 pair 数组同时存储每个数的值和它在原数组中的初始位置
    std::vector<std::pair<int, int>> val_idx(n);
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        val_idx[i] = {val, i};
    }

    // 按照数值大小对 pair 进行排序。
    // 排序后，val_idx[i] 就代表排名为 i+1 的数和它的初始位置
    std::sort(val_idx.begin(), val_idx.end());
    
    // 创建一个排名数组 p
    // p[初始位置] = 排名
    // 这样 p 就和原数组 a 的结构保持一致，但存的是排名
    std::vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        p[val_idx[i].second] = i + 1; // 使用 1-based 的排名，从 1 到 n
    }

    // dp[k] 将存储以排名 k 结尾的、排名连续的子序列的最长长度
    // 比如 dp[5] = 3 表示我们找到了一个以排名5结尾的，形如 [3, 4, 5] 的子序列
    std::vector<int> dp(n + 1, 0);
    int max_len = 0;

    // 遍历排名数组 p
    for (int i = 0; i < n; ++i) {
        int rank = p[i];
        // 状态转移方程：
        // 一个以 rank 结尾的连续排名序列的长度，
        // 是一个以 rank-1 结尾的序列长度加 1。
        // 因为我们从左到右遍历p，任何对dp[rank-1]有贡献的元素
        // 其在p中的位置一定在当前元素之前，天然满足了子序列的顺序要求。
        dp[rank] = dp[rank - 1] + 1;
        
        // 更新我们找到过的最长连续排名子序列的长度
        if (dp[rank] > max_len) {
            max_len = dp[rank];
        }
    }
    
    // 最少移动次数 = 总数 - 最多保留的数量
    std::cout << n - max_len << 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;
}

跑得快不快呀？

时间复杂度: O(N log N) 的说。
- 最耗时的部分是 std::sort，它的复杂度是 O(N log N)。
- 之后创建排名数组 p 和 DP 计算都只需要遍历一次数组，是 O(N) 的。
- 所以总的时间复杂度由排序决定，就是 O(N log N) 啦！对于这道题的数据范围来说，是绰绰有余的~
空间复杂度: O(N) 的说。
- 我们需要 val_idx 数组、排名数组 p 和 dp 数组来辅助计算，它们的大小都和 n 成正比，所以空间复杂度是 O(N)。

猫娘的小总结时间~

这道题真有趣，对吧！它教会了我们几件重要的事情喵：

逆向思维: 有时候，直接求解 "最少" 会很复杂，不妨想想如何求解 "最多"，比如本题的 "最少移动" vs "最多保留"。
问题转化: 把一个看似复杂的操作问题，转化为一个我们更熟悉的、经典的算法问题（最长子序列的变种），是解题的关键一步！
排名大法: 当元素的具体数值不重要，而它们的相对大小关系重要时，将它们转化为 1 到 n 的排名（或者叫离散化）是一个超级好用的技巧，能让问题变得更纯粹。
巧妙的DP: dp[rank] = dp[rank-1] + 1 这个状态转移非常简洁优美，它完美地利用了遍历顺序来隐式满足子序列的条件，值得我们学习和品味哦！

希望我的讲解能帮到主人！如果还有其他问题，随时可以再来问我哦，喵~ >w<

F1. Flying Sort (Easy Version) - 题解 ​

比赛与标签 ​

喵喵，这是什么任务呀？ ​

寻找不动的小鱼干喵~ ​

让代码动起来喵！ ​

跑得快不快呀？ ​

猫娘的小总结时间~ ​