CF2046 B 题解

· · 题解

首先，不难发现一点：如果一个数的后面有比它更小的数，那么这个更小的数挪到前面来一定更优，而如果没有比它更小的数字，进行操作则一定不优。这是由字典序的性质决定的。

于是就发现需要对所有在它后面存在比它更小的数的数进行操作。

发现挪的过程如果暴力做是 O(n) 的，但是我们其实并不需要把那些被挪走的数删掉，只需要打个标记就行了。而在尾端插入是很显然的。

通过观察样例发现一点：把数挪到尾端时不能胡乱来。因为可以按照数的大小排序，这样可以保证更优。

同样观察样例，发现并不是挪动一轮就可以完成的。有时挪了一轮之后会产生新的需要挪的数。于是还要再挪一轮。这第二轮也需要排序。

发现第二轮的数可以和第一轮放在一起排序，然后统一插入，而不是两轮单独排序。因为第一轮的数是必定要挪的，而在第一轮的数挪完之后第二轮的数也是必定要挪的，对于这些必定要挪的数，我们可以任意安排操作的顺序，所以可以放在一起统一排序插入以达到更优解。

我们还可以证明只需要两轮操作。因为在第一轮操作之后，没有被操作的数构成一个非降序列。第一轮操作的数都比任意没有被操作的数靠后，所以第二轮会操作所有大于第一轮操作的数中最小的数加一的数，并不会影响所有被操作的数中最小的数的大小。其余没有被操作的数不可能再比被操作的数更小了，而被操作了的数都已经被排好了序，也不可能产生新的需要操作的情况了。所以就是最优解了。

#include <bits/stdc++.h>

using namespace std;
int t, n;
vector<int> a;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        a.clear();

        cin >> n;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            a.push_back(x);
        }

        int min_val = 2e9;
        vector<int> tmp;
        for (int i = a.size() - 1; i >= 0; --i) {
            if (min_val < a[i]) {
                tmp.push_back(a[i] + 1);
                a[i] = -2e9;
            } else {
                min_val = a[i];
            }
        }

        sort(tmp.begin(), tmp.end());
        if (!tmp.empty()) {
            min_val = tmp.front();
        } else {
            min_val = 2e9;
        }

        for (int i = a.size() - 1; i >= 0; --i) {
            if (a[i] > 0) {
                if (min_val < a[i]) {
                    tmp.push_back(a[i] + 1);
                    a[i] = -2e9;
                } else {
                    min_val = a[i];
                }
            }
        }

        sort(tmp.begin(), tmp.end());
        for (auto i: tmp) {
            a.push_back(i);
        }
        tmp.clear();

        for (auto i: a) {
            if (i > 0) {
                cout << i << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}