题目描述
难度分:$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]$时:
- 如果后面有比$s[i]$小的数字,那么要把$s[i]$移到后面去就会变为$s[i]+1$,最终方案会增加$s[i]+1$的频数,将最终方案的数字频数记录在$cnt_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;
}