#P0019. 交换到最大
交换到最大
题目描述
给你一个由 至 的数字组成的字符串 。在一次运算中,您可以选取该字符串中除 或最左边数字之外的任意数字,将其减少 ,然后将其与左边的数字对调。
例如,从字符串 中进行一次运算,可以得到 或 。
找出任意多次运算后所能得到的字典序最大的字符串。
输入格式
输入的第一行是一个整数 ( ) - 测试用例的数量。
每个测试用例由一行数字字符串 ( ) 组成,其中 表示 的长度。字符串不包含前导零。
保证所有测试用例的 之和不超过 。
输出格式
对于每个测试用例,在单独一行中打印其对应的答案。
样例 #1
样例输入 #1
6
19
1709
11555
51476
9876543210
5891917899
样例输出 #1
81
6710
33311
55431
9876543210
7875567711
样例解释
在第一个样例中,以下操作顺序是合适的: .
在第二个样例中,适合使用以下操作序列: $1709 \rightarrow 1780 \rightarrow 6180 \rightarrow 6710$ .
在第四个样例中,以下操作序列是合适的: $51476 \rightarrow 53176 \rightarrow 53616 \rightarrow 53651 \rightarrow 55351 \rightarrow 55431$ .