题目描述

难度分:$1200$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，仅包含0到9。

你可以执行如下操作任意次：

• 把$s$中的一个字符$c$删除，然后在任意位置插入$min(c+1,9)$。

输出你能得到的字典序最小的字符串。

输入样例

4
04829
9
01
314752277691991

输出样例

02599
9
01
111334567888999

算法

思维题

由于$9$移动到后面去不会变成更大的数，所以所有的$9$都可以直接移动到末尾排好。而$[1,8]$中的整数$x$要移动到后面去都会使得$x$变成$x+1$，是有代价的。因为我们希望最终$s$串中的数字要按照升序排列好，所以要把大的数往后移。

因此我们可以倒序遍历$s$串，用一个$cnt_1$数组记录子串$(i,n]$中每个数字的频数，$cnt_2$记录最终方案的每个数字频数。当遍历到$s[i]$时：

1. 如果后面有比$s[i]$小的数字，那么要把$s[i]$移到后面去就会变为$s[i]+1$，最终方案会增加$s[i]+1$的频数，将最终方案的数字频数记录在$cnt_2$中。
2. 否则最终方案就会增加一个$s[i]$，也记录在$cnt_2$中。

倒序遍历完$s$串后，按照$cnt_2$输出最终方案即可。

复杂度分析

时间复杂度

倒序遍历一遍$s$串就可以得到最终方案里每个数字的频数，而对于每个数字字符$s[i]$，需要检查它的后面有没有比自己小的数字字符，这时候需要遍历$0$~$9$的后缀频数进行检查。因此，算法整体的时间复杂度为$O(n\Sigma)$，$\Sigma$是字符集大小，本题中为$10$。

空间复杂度

需要两个频数统计表$cnt_1$和$cnt_2$，$cnt_1$是在倒序遍历$s$的过程中子串$(i,n]$的数字频数，$cnt_2$是最终方案的每个数字频数。它们两个的空间消耗都是$O(\Sigma)$，这也是整个算法的额外空间复杂度。

C++ 代码

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

using namespace std;
const int N = 200010;
int T, n, cnt1[10], cnt2[10];
char s[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        for(int i = n; i >= 1; i--) {
            int digit = s[i] - '0';
            if(digit == 9) {
                cnt2[digit]++;
                continue;
            }
            bool has_greater = false;
            for(int num = 0; num < digit; num++) {
                if(cnt1[num] > 0) {
                    cnt2[digit + 1]++;
                    has_greater = true;
                    break;
                }
            }
            if(!has_greater) cnt2[digit]++;
            cnt1[digit]++;
        }
        for(int digit = 0; digit <= 9; digit++) {
            for(int i = 0; i < cnt2[digit]; i++) {
                printf("%d", digit);
            }
        }
        puts("");
    }
    return 0;
}