B. 通过操作得到最小字典序数组 详细题解

问题描述

给定一个长度为 $n$ 的数组 $a$，可以多次执行操作：选择一个下标 $i$，令 $a_i := a_i + 1$，然后将该元素移动到数组末尾。求通过若干次操作后能得到的字典序最小的数组。

关键观察

1. 每个元素最多被移动一次
   如果同一个元素被移动两次，第一次移动后它已经在末尾，第二次移动会再将它移到末尾（同时再增加 $1$）。但这两次操作可以合并为一次：直接将该元素增加 $2$ 并移到末尾。因此，最优解中每个元素至多被移动一次。

2. 被移动元素的最终顺序
   假设我们决定将某个子集的元素各移动一次（其余元素保持原位且不增加）。移动时，我们可以任意选择操作顺序。由于被移动的元素最终都出现在数组末尾，且它们被增加 $1$，为了得到字典序最小的结果，我们应该将这些被移动的元素按照值从小到大的顺序放置在末尾（因为字典序比较是从左到右，末尾的值只有在前面都相同时才起作用）。因此，移动元素的最终顺序就是它们加 $1$ 后的升序。

3. 未被移动的元素保持原顺序
   未被移动的元素留在原位置（不增加），且它们的相对顺序不变。它们会出现在结果数组的前部，紧接在后面的就是被移动并排序后的元素。

贪心策略

为了得到字典序最小的数组，我们希望尽可能让前面的元素小。

• 第一个位置的最小可能值显然是整个数组的最小值。为了把它放到第一个位置，它前面所有的元素都必须被移动（因为它们会挡住它）。这些被移走的元素会被增加 $1$ 并放到末尾。
• 在第一个位置确定为最小值后，第二个位置可以从剩下的元素中选择：要么是原数组中最小值右侧的最小值（未被移动），要么是被移动的元素中增加 $1$ 后的最小值。
• 继续这个过程：我们不断从尚未被移动的元素中选取最小的那个（如果它没有被前面的元素挡住），如果它被挡住了（即它前面还有未移动的元素），那么它就不能直接放在当前位置，必须把它前面的元素移走。实际上，我们可以统一用“后缀最小值”序列来描述。

更具体地，定义后缀最小值数组：从右向左扫描，记录当前遇到的最小值。这些后缀最小值就是不会被移动的候选元素，因为任何比它小的元素一定在它右边（否则它就不是后缀最小值）。实际上，结果的前缀部分就是由这些后缀最小值（按原序）组成的，直到某个点之后，剩余的元素都被移动。

证明：
设原数组为 $a_1, a_2, \dots, a_n$。令 $b_i = \min_{j \ge i} a_j$（后缀最小值）。则 $b_i$ 是非递减的（因为从右向左，最小值只会变小或不变）。
考虑我们最终得到的结果数组 $c$。第一个元素一定是 $b_1$（全局最小值）。为了取出它，所有在它前面的元素 $a_1,\dots,a_{k-1}$（其中 $k$ 是第一个最小值的位置）都必须被移动。这些被移动的元素加 $1$ 后进入后面的集合。
第二个位置，我们需要从剩余元素（原数组中 $k$ 之后的部分，以及被移动的加一后的元素）中选最小的。如果 $b_{k+1}$ 比所有被移动元素加一后的最小值还小，那么第二个元素就是 $b_{k+1}$，并且它前面（在 $k$ 之后）的元素又需要被移动……依此类推。
这个贪心过程就是不断取出未被移动的后缀最小值，直到某个时刻，被移动元素中的最小值小于等于下一个后缀最小值，这时所有剩余的原数组元素都应被移动（因为它们不可能比当前已有的最小值更优）。此时，我们把所有剩余原数组元素（包括当前后缀最小值及其后面的）全部加 $1$，然后与之前已移动的元素合并排序，就得到最终的末尾部分。

算法实现（标程思路）

标程使用了一个双端队列（用数组模拟）front 来存储未被移动的后缀最小值序列，以及一个多重集合 back 存储被移动元素加 $1$ 后的值。

具体步骤（从右向左扫描）：

1. 初始化一个空的双端队列 front（实际用数组 front 和两个指针 frontfront, frontback 表示），以及空的多重集 back。
2. 从 $i=n-1$ 到 $0$ 遍历原数组：
   • 如果当前 front 为空，或者 $a_i$ 小于等于 front 的第一个元素（即当前后缀最小值），则把 $a_i$ 插入到 front 的头部（即成为新的后缀最小值）。
   • 否则，说明 $a_i$ 不是后缀最小值，它一定会在后续被移动，所以直接将其加 $1$ 后放入 back 中。
   • 然后，检查 front 的最后一个元素（即当前未被移动的最大后缀最小值）是否大于 back 中的最小值。如果是，说明这个 front 的末尾元素应该被移动（因为它比已经移动的元素加一后还大），于是把它从 front 尾部弹出，加 $1$ 后放入 back。重复此过程直到不再需要移动。
3. 扫描结束后，front 中剩下的元素就是最终保留在原位（不移动）的部分，它们按原顺序（从左到右）就是结果的前缀。
4. back 中的元素是那些被移动过（加 $1$）的元素，将它们排序后（back 本身是多重集，自动有序）追加到结果后面。

这个算法保证了得到的数组字典序最小。

复杂度分析

• 每个元素最多进入 front 一次，从 front 弹出一次，进入 back 一次。back 使用 multiset，插入和删除均为 $O(\log n)$。
• 总时间复杂度 $O(n \log n)$，空间 $O(n)$。
• 由于所有测试用例的 $n$ 总和不超过 $10^5$，该复杂度完全可以接受。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> front(n);
    int l = n, r = n;   // [l, r) 是 front 中有效区间
    multiset<int> back;
    for (int i = n-1; i >= 0; --i) {
        if (l >= r || a[i] <= front[l]) {
            front[--l] = a[i];
        } else {
            back.insert(a[i] + 1);
        }
        while (l < r && !back.empty() && front[r-1] > *back.begin()) {
            back.insert(front[r-1] + 1);
            --r;
        }
    }
    vector<int> ans;
    for (int i = l; i < r; ++i) ans.push_back(front[i]);
    for (int x : back) ans.push_back(x);
    for (int i = 0; i < (int)ans.size(); ++i) {
        cout << ans[i] << " \n"[i+1 == ans.size()];
    }
}

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