E1. Permutation Minimization by Deque - 题解

比赛与标签

比赛: Codeforces Round 744 (Div. 3) 标签: constructive algorithms, greedy, math 难度: *1000

题目大意喵~

主人你好呀~！这道题目是说，我们拿到一个大小为 n 的排列 p（也就是 1 到 n 每个数字都只出现一次的数组）。然后呢，我们有一个空空如也的双端队列（deque）。

我们要按照 p 的顺序，从 p_1 到 p_n，一个一个地把数字放进这个双端队列里。每次放一个数字进去的时候，我们都可以自己决定是把它放在队列的 最前面 还是 最后面。

等所有 n 个数字都放进去之后，双端队列里就会形成一个新的排列。我们的任务，就是通过巧妙地选择每次是放前面还是放后面，让最终队列里的这个排列的 字典序最小，然后把它打印出来，喵~

举个栗子，如果 p = [3, 1, 2, 4]：

处理 3：队列是空的，只能放进去 -> [3]
处理 1：可以放前面 [1, 3]，也可以放后面 [3, 1]。
处理 2：...
处理 4：...

我们的目标就是找到一种操作方法，使得最后得到的序列字典序最小。比如对于 [3, 1, 2, 4]，答案就是 1 3 2 4 啦！

解题思路喵！

这道题要求我们构造一个字典序最小的序列，一看到“字典序最小”，我们的第一反应就应该是：要让序列最前面的数字尽可能小！对不对呀？

这就像排队一样，要让整个队伍看起来最“矮”，肯定要让最前面的人最矮，然后再让第二个人尽量矮，以此类推，喵~

所以，我们可以得出一个非常重要的 贪心策略 呐！

当我们处理排列 p 中的第 i 个元素 p[i] 时，我们来看看双端队列 dq 的情况：

如果队列是空的：没得选啦，只能把 p[i] 放进去。此时队列里就是 [p[i]]。
如果队列不是空的：这时候我们就有选择了！
- 我们可以把 p[i] 放到队头（push_front）。
- 我们也可以把 p[i] 放到队尾（push_back）。
让我们想想，哪种选择对字典序更有利呢？假设现在队头的元素是 dq.front()。
- 如果我们把 p[i] 放到队头，新的序列将以 p[i] 开头。
- 如果我们把 p[i] 放到队尾，序列将仍然以 dq.front() 开头。
为了让整个序列的字典序最小，我们必须优先保证队头元素最小。所以：
- 当 p[i] < dq.front() 时：哇！我们找到了一个比当前队头还小的数字！为了让字典序更小，我们当然应该毫不犹豫地把它放到队头，让它成为新的、更小的队头！这样做肯定是最优的，喵~
- 当 p[i] > dq.front() 时：如果把 p[i] 放到队头，新的队头就变成了 p[i]，比原来的 dq.front() 要大。这会让整个序列的字典序变大，是我们不希望看到的！所以，为了保住我们当前已经很小的队头 dq.front()，我们唯一的选择就是把 p[i]乖乖地放到队尾去。

总结一下我们的贪心策略就是：对于每一个要处理的数字，将它与当前双端队列的队头元素比较。如果它比队头元素小，就把它插到队头；否则，就插到队尾。

这个简单的策略保证了在每一步，我们都尽力让队头元素保持最小，从而实现了全局的字典序最小，是不是很神奇的说！

代码实现的说

cpp

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main() {
    // 加速输入输出，让程序跑得更快喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t; // 读取测试用例的数量
    while (t--) {
        int n;
        cin >> n; // 读取排列的大小
        vector<int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i]; // 读取排列 p
        }

        // 创建一个双端队列来构造我们的答案
        deque<int> dq;

        // 遍历输入的排列 p
        for (int i = 0; i < n; i++) {
            // 如果队列是空的，这是第一个元素，直接加到后面（或前面，效果一样）
            if (dq.empty()) {
                dq.push_back(p[i]);
            } else {
                // 如果当前元素 p[i] 比队头元素小
                // 为了让字典序最小，我们把它放到队头
                if (p[i] < dq.front()) {
                    dq.push_front(p[i]);
                } else {
                    // 否则，为了不破坏当前最小的队头
                    // 我们只能把它放到队尾
                    dq.push_back(p[i]);
                }
            }
        }

        // 打印最终在双端队列里的结果
        for (int i = 0; i < dq.size(); i++) {
            if (i > 0) cout << " "; // 在数字之间打印空格
            cout << dq[i];
        }
        cout << '\n'; // 每个测试用例后换行
    }
    return 0;
}

复杂度分析

时间复杂度: O(n) 的说。对于每个测试用例，我们只需要遍历一次大小为 n 的输入排列。在循环中，对双端队列的操作（push_front, push_back, front）的平均时间复杂度都是 O(1)。所以总的时间复杂度就是线性的 O(n) 啦，非常高效！
空间复杂度: O(n) 的说。我们用了一个双端队列来存储所有的 n 个元素，所以需要 O(n) 的额外空间。

知识点与总结喵~

这真是一道可爱又经典的题目呢！通过它我们可以学到：

贪心算法 (Greedy Algorithm): 这道题的核心就是贪心。我们不需要考虑未来的复杂情况，只需要在每一步都做出当前看起来最好的选择（即，尽力让队头元素变小），最终就能得到全局最优解。这是贪心思想的完美体现！
双端队列 (Deque): 这个数据结构是解决本题的关键工具！它支持在两端进行 O(1) 的插入和删除操作，完美契合了我们“放到队头”或“放到队尾”的需求。如果用普通数组或 vector 来模拟，在头部插入元素会是 O(n) 的，那就太慢了喵。
字典序 (Lexicographical Order): 理解字典序是解题的出发点。要让字典序最小，就要从第一位开始，让它尽可能小。这个原则指导了我们整个贪心策略的设计。

总之，当你遇到要求构造“最小”或“最大”结果的问题时，不妨先从贪心的角度思考一下，看看能不能找到一个简单的局部最优策略，也许它就能通向正确的答案哦！希望这篇题解能帮到你，加油喵~！

E1. Permutation Minimization by Deque - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现的说 ​

复杂度分析 ​

知识点与总结喵~ ​