喵哈~ 主人，今天由我来为你讲解一道有趣的构造题，Codeforces 1506E - Restoring the Permutation。这道题需要一点点小聪明，不过别担心，跟着我的思路，很快就能把它解决掉啦，喵~

题目大意

首先，我们来理解一下题目在说什么吧！

• 排列 (Permutation)：一个长度为 n 的排列 p，是由 1 到 n 这 n 个整数组成的序列，其中每个数都恰好出现一次。比如说 [1, 3, 2] 就是一个长度为 3 的排列，但 [1, 2, 2] 就不是，因为 2 出现了两次。

• 变换规则：有一个神秘的规则，可以把一个排列 p 变成一个数组 q。规则是这样的：q 的第 i 个元素 q_i 是 p 的前 i 个元素中的最大值，也就是 q_i = max(p_1, p_2, ..., p_i)。这个 q 数组也被称为 p 的前缀最大值数组。

• 任务：现在我们只知道变换后的数组 q，原来的排列 p 已经不见了 (´• ω •)。我们需要找出两个可能生成这个 q的原始排列p`：

  1. 字典序最小的排列 p_min。
  2. 字典序最大的排列 p_max。

小提示喵：什么是字典序呢？就像查字典一样，从左到右比较两个序列。第一个不同的位置上，元素较小的那个序列，字典序就更小。比如 [1, 3, 2] 就比 [1, 3, 4] 字典序小。

举个例子，如果 p = [3, 2, 4, 1, 7, 5, 6]，那么 q 就是 [3, 3, 4, 4, 7, 7, 7]。 对于这个 q，字典序最小的 p 是 [3, 1, 4, 2, 7, 5, 6]，字典序最大的 p 是 [3, 2, 4, 1, 7, 6, 5]。

题解方法

这道题的关键在于分析 p 和 q 之间的关系，找到一些确定的信息，然后根据这些信息去构造我们想要的排列。

我们从头开始构造排列 p。当我们确定 p_i 的值时，会发现有两种情况：

1. 当 q_i > q_{i-1} 时 (对于 i=1 也一样，可以认为 q_0 = 0)： q_i 是 p_1, ..., p_i 的最大值，而 q_{i-1} 是 p_1, ..., p_{i-1} 的最大值。既然 q_i 比 q_{i-1} 大，说明新的最大值一定是 p_i 带来的！所以，在这种情况下，p_i 的值是唯一确定的，它必须等于 q_i。这是我们解题的突破口哦，喵！

2. 当 q_i == q_{i-1} 时： 这说明 p_i 的值并没有超过前面的最大值 q_{i-1}，也就是 p_i <= q_{i-1}。同时，p_i 还必须是一个在 p_1, ..., p_{i-1} 中没有出现过的数字。

有了这个发现，我们就可以使用贪心策略来构造字典序最小和最大的排列了。我们从左到右，一位一位地确定 p_i 的值。

构造字典序最小的排列 p_min

为了让整个排列的字典序最小，我们希望在每个位置 i 都填上尽可能小的数字。

• 当 q_i > q_{i-1} 时，p_i 别无选择，只能是 q_i。
• 当 q_i == q_{i-1} 时，我们需要从还未使用过的数字中，选择一个最小的填入 p_i。

那么，哪些数字是“未使用过”的呢？ 当我们确定 p_i = q_i 时，我们不仅用掉了 q_i 这个数，还知道了一件事：从 q_{i-1} + 1 到 q_i - 1 这些数字，虽然小于 q_i，但它们都没有成为过前缀最大值。这意味着它们可以在后面的“缝隙”（即 q_j = q_{j-1} 的位置）中被使用。

所以，我们可以维护一个“可用数字池”。

1. 当我们遇到 q_i > q_{i-1} 时，我们就把 q_{i-1} + 1 到 q_i - 1 的所有数字都扔进这个池子里。
2. 当我们遇到 q_i == q_{i-1} 时，就从池子里拿出最小的一个数填入 p_i。

用什么来当这个“池子”最方便呢？当然是**小顶堆（最小优先队列）**啦！它能帮我们自动维护池子里的最小值，每次直接取出来用就好，非常方便喵~

构造字典序最大的排列 p_max

思路完全一样，只是我们的贪心策略变了。为了让整个排列的字典序最大，我们希望在每个位置 i 都填上尽可能大的数字。

• 当 q_i > q_{i-1} 时，p_i 依然只能是 q_i。
• 当 q_i == q_{i-1} 时，我们需要从“可用数字池”中，选择一个最大的填入 p_i。

这次，我们需要一个能随时取出最大元素的池子，所以我们用大顶堆（最大优先队列） 就好啦。

总结一下两个算法：

• 求 p_min: 遍历 q，用一个小顶堆存放备用数字。
• 求 p_max: 遍历 q，用一个大顶堆存放备用数字。

两个过程几乎一模一样，只是用的堆不同。

题解代码

这是 C++ 的实现代码，我已经加上了一些可爱的注释，希望能帮助主人更好地理解，喵~

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

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

    // --- 计算字典序最小的排列 p_min 喵~ ---
    {
        // 用一个小顶堆来存放可以填入的、还未使用的数字
        std::priority_queue<int, std::vector<int>, std::greater<int>> available_nums;
        std::vector<int> p_min(n);
        int last_q = 0; // 记录上一个不同的 q 值

        for (int i = 0; i < n; ++i) {
            if (q[i] > last_q) {
                // p_i 必须是 q_i 呢，这是新的前缀最大值
                p_min[i] = q[i];
                // 从 last_q + 1 到 q_i - 1 的这些数字，现在都可以用了哦
                for (int j = last_q + 1; j < q[i]; ++j) {
                    available_nums.push(j);
                }
                last_q = q[i];
            } else { // q[i] == last_q
                // p_i 可以填一个之前省下来的数字，为了字典序最小，就填最小的那个吧！
                p_min[i] = available_nums.top();
                available_nums.pop();
            }
        }
        for (int i = 0; i < n; ++i) {
            std::cout << p_min[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << "\n";
    }

    // --- 计算字典序最大的排列 p_max 喵~ ---
    {
        // 这次用一个大顶堆，因为我们想要最大的备用数字
        std::priority_queue<int> available_nums;
        std::vector<int> p_max(n);
        int last_q = 0;

        for (int i = 0; i < n; ++i) {
            if (q[i] > last_q) {
                // 和上面一样，p_i 必须是 q_i
                p_max[i] = q[i];
                // 备用数字池也是一样的
                for (int j = last_q + 1; j < q[i]; ++j) {
                    available_nums.push(j);
                }
                last_q = q[i];
            } else { // q[i] == last_q
                // 为了字典序最大，这次我们贪心地选择最大的那个备用数字！
                p_max[i] = available_nums.top();
                available_nums.pop();
            }
        }
        for (int i = 0; i < n; ++i) {
            std::cout << p_max[i] << (i == n - 1 ? "" : " ");
        }
        std::cout << "\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题用到了一些基础但很重要的知识点，我们来复习一下吧！

1. 贪心算法 (Greedy Algorithm) 贪心算法就是每一步都做出当前看起来最好的选择，并期望通过一系列的局部最优解，最终达到全局最优解。就像猫猫总是会选择最舒服的地方晒太阳一样喵~ 在这道题里，为了让字典序最小/最大，我们在每个能选择的位置都填上当前可选的最小/最大值，这就是一种典型的贪心思想。

2. 优先队列 (Priority Queue) 优先队列是一个很神奇的数据结构，你可以把它想象成一个特殊的口袋。放进去的东西，它会自动帮你排序。你可以随时拿出最大（大顶堆）或者最小（小顶堆）的那个元素。它通常用堆 (Heap) 实现，插入和删除最值的时间复杂度都是 O(log N)，非常高效。在这道题里，它完美地扮演了“可用数字池”的角色，帮助我们快速找到需要填入的数字。

3. 字典序 (Lexicographical Order) 这是一种比较两个序列大小的方法。在算法竞赛中非常常见，尤其是在构造题和字符串问题里。理解它的定义是解决这类问题的基础哦。

好啦，这道题就被我们轻松解决啦！通过分析题目性质，找到确定部分，再对不确定的部分使用贪心策略，最后借助合适的数据结构高效实现。主人是不是又变强了呀？下次再一起玩耍吧，喵~ (ฅ'ω'ฅ)