NekoNowcoder

Appearance

DropVoicing - 题解 ​

标签与难度 ​

标签: 动态规划, 最长上升子序列, LIS, 环形数组, 思维题 难度: 1900

题目大意喵~ ​

主人，这道题是关于音乐和排列的，听起来就很有趣对吧，喵~？

我们有一个包含 nn 个不同音符的和弦，用一个 11 到 nn 的排列 pp 来表示。我们可以对这个排列进行两种操作：

  1. Drop-2: 把倒数第二个音符 pn−1p_{n-1} 拿出来，放到最前面。
  2. Invert: 把第一个音符 p1p_1 拿出来，放到最后面。

我们可以连续进行任意多次 Drop-2 操作，这样一连串的操作被称为一次 "multi-drop"。在两次 "multi-drop" 之间，我们可以进行任意次数的 Invert 操作。

我们的目标是，通过最少次数的 "multi-drop"，将初始排列 pp 变成有序的 1, 2, ..., n。请你帮忙计算这个最少的次数，喵~

举个栗子：如果 p=(1,3,2)p = (1, 3, 2)，Invert 操作会把它变成 (3,2,1)(3, 2, 1)。Drop-2 操作会把 pn−1=p2=3p_{n-1}=p_2=3 移到最前，变成 (3,1,2)(3, 1, 2)。

解题思路分析 ​

喵~ 这道题的操作看起来有点绕，特别是那个 "multi-drop"，直接去模拟操作序列会让人头晕的。所以，我们不妨换个角度来思考这个问题，呐。

操作的本质是什么？ ​

首先，我们来分析一下这两个操作。

  • Invert 操作: (p_1, p_2, ..., p_n) 变成 (p_2, ..., p_n, p_1)。这不就是一个循环左移嘛！因为我们可以在两次 multi-drop 之间无限次使用它，这意味着我们可以不花任何代价（multi-drop次数），就把排列变成它的任意一个循环同构形式。比如，p=(a,b,c,d)，我们可以免费得到 (b,c,d,a), (c,d,a,b) 和 (d,a,b,c)。这给了我们很大的自由度，我们可以选择一个对我们最有利的循环排列作为起点，再进行 multi-drop。

  • Multi-drop 操作: 这是一连串的 Drop-2。一次 Drop-2 是把 pn−1p_{n-1} 移到最前面。这个操作的意义在于，它能够移动一个元素，从而改变排列的结构。一次 multi-drop 是我们计算成本的单位。

问题的转化 ​

我们的目标是得到 1, 2, ..., n 这个完全有序的排列。反过来想，我们希望尽可能多地保留一些元素，让它们不动，只移动那些“不听话”的捣乱分子。

哪些元素算是“听话”的呢？当然是那些已经排好序的元素啦！也就是说，如果我们在某个排列中，能找到一个子序列，它们的值是递增的，比如 (..., 2, ..., 5, ..., 8, ...)，那么这几个元素 2, 5, 8 的相对顺序就是正确的。我们最希望的就是保留这样的子序列。

结合 Invert 操作，我们可以从任意一个循环班底开始。那么，我们应该选择哪个班底呢？当然是那个拥有最长上升子序列 (Longest Increasing Subsequence, LIS) 的循环班底！因为这个最长的上升子序列，就是我们能保留的、相对顺序正确的最大元素集合。

假设我们找到了这个最长的“可保留”的子序列，它的长度是 LL。这个子序列存在于 p 的某个循环同构形式中。那么，总共有 nn 个元素，我们保留了 LL 个，剩下 n−Ln-L 个就是“捣乱分子”，是我们需要通过 multi-drop 操作去移动的。

虽然题目中的 Drop-2 操作很奇特，但配合上无限制的 Invert，可以证明（虽然过程有点小复杂，喵~），一次 multi-drop 的核心作用，就是可以有效地将一个“捣乱分子”从当前的位置拿出来，重新安置，从而让它不再干扰我们保留的那个上升子序列。

因此，有多少个“捣dan份子”，我们就需要多少次 multi-drop 来“教育”它们。所以，最终的答案就是：

最少 multi-drop 次数=n−L\text{最少 multi-drop 次数} = n - L

其中 LL 是原排列所有循环同构形式中，LIS 长度的最大值。我们把这个值称为最长循环上升子序列 (Longest Circular Increasing Subsequence, LCIS) 的长度。

如何求解 LCIS？ ​

找到了问题的核心，接下来就是算法实现了，喵！ 求解一个环形排列的 LCIS 有一个非常经典的技巧：

  1. 破环成链: 我们把原来的长度为 nn 的数组 pp 复制一份，拼在它自己后面，形成一个长度为 2n2n 的新数组 p_doubled。例如，p = (3, 1, 4, 2)，那么 p_doubled = (3, 1, 4, 2, 3, 1, 4, 2)。

  2. 枚举起点: p 的所有 nn 个循环同构形式，就对应了 p_doubled 中从索引 0 到 n-1 开始的、长度为 nn 的所有子数组。

    • p_doubled[0...n-1] = (3, 1, 4, 2) (原始排列)
    • p_doubled[1...n] = (1, 4, 2, 3) (循环左移1次)
    • p_doubled[2...n+1] = (4, 2, 3, 1) (循环左移2次)
    • p_doubled[3...n+2] = (2, 3, 1, 4) (循环左移3次)

  3. 求解并取最大值: 我们对这 nn 个子数组，分别求它们的 LIS 长度，然后取一个最大值，这个最大值就是我们想要的 LL。

如何高效求解 LIS？ ​

求解 LIS 有两种常见方法：

  1. O(N2)O(N^2) 动态规划: dp[i] 表示以第 i 个元素结尾的 LIS 长度。dp[i] = 1 + max({dp[j]})，其中 j < i 且 a[j] < a[i]。
  2. O(Nlog⁡N)O(N \log N) 贪心 + 二分查找: 维护一个数组 tails，其中 tails[i] 表示所有长度为 i+1 的上升子序列中，末尾元素的最小值。遍历原数组，对于每个元素 x，在 tails 中找到第一个不小于 x 的位置并替换它。如果 x 比 tails 中所有元素都大，就把它加到末尾。tails 的长度就是 LIS 的长度。

考虑到本题 NN 的范围可能达到 500，总的时间复杂度会是 N×(LIS 算法复杂度)N \times (\text{LIS 算法复杂度})。如果用 O(N2)O(N^2) 的 LIS，总复杂度是 O(N3)O(N^3)，可能会超时。所以我们选择 O(Nlog⁡N)O(N \log N) 的 LIS 算法更保险，总复杂度为 O(N2log⁡N)O(N^2 \log N)，稳稳的，喵~

总结一下我们的解题步骤：

  1. 读入排列 pp。
  2. 将 pp 复制一份拼在后面，得到 2n2n 长的数组 p_doubled。
  3. 初始化一个 max_lis = 0。
  4. 循环 ii 从 00 到 n−1n-1： a. 取出 p_doubled 中从 ii 开始，长度为 nn 的子数组。 b. 用 O(Nlog⁡N)O(N \log N) 的方法计算该子数组的 LIS 长度，记为 current_lis。 c. 更新 max_lis = max(max_lis, current_lis)。
  5. 输出 n - max_lis。

这样，问题就解决啦！是不是感觉清晰多了？喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码哦！注释很详细，希望能帮到你，喵~

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

// 使用贪心+二分查找，计算一个序列的最长上升子序列(LIS)
// 时间复杂度: O(N log N)
int calculate_lis(const std::vector<int>& arr) {
    if (arr.empty()) {
        return 0;
    }
    
    // tails[i] 存储的是所有长度为 i+1 的上升子序列中，末尾元素的最小值
    std::vector<int> tails;
    
    for (int num : arr) {
        // lower_bound 找到第一个不小于 num 的元素的位置
        // 如果 num 比 tails 中所有元素都大，it 会指向 tails.end()
        auto it = std::lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            // num 比所有已知 LIS 的末尾元素都大，可以构成一个更长的 LIS
            tails.push_back(num);
        } else {
            // 找到了一个长度为 (it - tails.begin() + 1) 的 LIS
            // 它的末尾元素是 *it。现在我们发现可以用更小的 num 来结尾
            // 这有助于将来接上更多的元素，所以更新它
            *it = num;
        }
    }
    
    return tails.size();
}

int main() {
    // 加速输入输出，让我跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

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

    std::vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> p[i];
    }

    // 技巧：将数组复制一份拼在后面，方便处理环形问题
    std::vector<int> p_doubled(2 * n);
    for (int i = 0; i < n; ++i) {
        p_doubled[i] = p[i];
        p_doubled[i + n] = p[i];
    }

    int max_lcs_length = 0;

    // 遍历所有 n 个循环同构的子序列
    for (int i = 0; i < n; ++i) {
        // 构造一个代表循环同构的子序列
        std::vector<int> current_permutation;
        current_permutation.reserve(n);
        for (int j = 0; j < n; ++j) {
            current_permutation.push_back(p_doubled[i + j]);
        }
        
        // 计算这个子序列的 LIS 长度
        int current_lis = calculate_lis(current_permutation);
        
        // 更新我们找到的最大 LIS 长度
        if (current_lis > max_lcs_length) {
            max_lcs_length = current_lis;
        }
    }

    // 答案是 n 减去最长的可保留子序列的长度
    std::cout << n - max_lcs_length << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N2log⁡N)O(N^2 \log N) 我们有一个外层循环，遍历 nn 个不同的循环起点，这是 O(N)O(N)。在循环内部，我们对一个长度为 nn 的子数组调用 calculate_lis 函数。这个函数使用二分查找，其时间复杂度是 O(Nlog⁡N)O(N \log N)。所以总的时间复杂度是 N×O(Nlog⁡N)=O(N2log⁡N)N \times O(N \log N) = O(N^2 \log N)。对于 N≤500N \le 500 的数据规模，这个复杂度是完全可以接受的，喵！

  • 空间复杂度: O(N)O(N) 我们创建了一个长度为 2N2N 的 p_doubled 数组，这是 O(N)O(N)。在 calculate_lis 函数中，tails 数组最多也只会增长到 NN，也是 O(N)O(N)。因此，总的空间复杂度是 O(N)O(N)。

知识点总结 ​

这道题真是一次有趣的思维旅行，对吧？我们来总结一下学到了什么，喵~

  1. 问题转化: 面对复杂的操作定义时，不要陷入细节，尝试从目标出发，思考操作的本质。这里，"免费的循环位移" 和 "有代价的元素移动" 是关键。
  2. 最长上升子序列 (LIS): 这是解决许多排列和序列问题的基石。理解“保留一个 LIS，移动其他元素”是常见的解题模式。
  3. 环形问题处理: "破环成链"（即复制数组拼接在后）是处理环形数组问题的万能钥匙！无论是求环形子数组和、还是环形 LIS，这个技巧都非常有用。
  4. 高效 LIS 算法: 掌握 O(Nlog⁡N)O(N \log N) 的 LIS 算法是很有必要的，它比 O(N2)O(N^2) 的 DP 在数据规模较大时有明显优势。

希望这篇题解能帮到你，如果还有问题，随时可以再来找我哦，喵~