题目描述

难度分:$1400$

输入长度$\leq 10^5$的字符串$s$，只包含字符012。

一次操作，你可以交换任意一对相邻的0和1，或者相邻的1和2。

你可以操作任意次。

注意你不能交换相邻的0和2。

输出字典序最小的$s$。

输入样例$1$

100210

输出样例$1$

001120

输入样例$2$

11222121

输出样例$2$

11112222

输入样例$3$

20

输出样例$3$

20

算法

贪心构造

这个题的贪心策略感觉还是不太显然的，先过滤掉两种特殊情况：如果$s$中没有0或2，那直接把$s$排序后输出就行；如果$s$中没有1，那$s$就不能做任何交换，直接输出。

对于一般情况，可以发现任何的0都是会被它前面的2给阻断的，因此0绝对不可能翻越它前面的任何一个2。而1是个万精油，可以和0换，也可以和2换，所以可以无限往前面换。这时候做个分类讨论就好了：

1. 如果第一个2前面没有任何0，就把所有的1换到最前面，0和2保持相对顺序不变。
2. 否则第一个2前面的0先占领最前面，然后把$s$中的所有1紧接其后，最后剩下的0和2保持相对顺序不变。

复杂度分析

时间复杂度

整个算法过程只是在贪心地构造答案，如果不排序，是可以做到$O(n)$的（排序就是$O(nlog_2n)$）。

空间复杂度

输出的答案串需要构造一个新串出来，否则直接交换原串中的字符不能保证$O(n)$的时间复杂度，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int cnt[3] = {0};
    for(char c: s) cnt[c - '0']++;
    if(cnt[0] == 0 || cnt[2] == 0) {
        sort(s.begin(), s.end());     // 可以不排序直接构造
        cout << s << endl;
    }else if(cnt[1] == 0) {
        cout << s << endl;
    }else {
        int first2 = s.find('2'), first0 = s.find('0');
        if(first2 < first0) {
            // 只要最左边的0左边有2，0就不可能被移动到最左边，此时让1无限往前面移，0和2保持相对位置不变
            string ans = string(cnt[1], '1');
            for(char c: s) {
                if(c == '0' || c == '2') {
                    ans.push_back(c);
                }
            }
            cout << ans << endl;
        }else {
            string ans;
            for(int i = 0; i < first2; i++) {
                if(s[i] == '0') {
                    ans.push_back('0');
                }
            }
            ans += string(cnt[1], '1');
            for(int i = first2; i < n; i++) {
                if(s[i] != '1') ans.push_back(s[i]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}