首页 > 试题广场 >

交换到最大

[编程题]交换到最大

热度指数：2426 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个仅由数字 $\texttt{0-9}$ 构成的字符串 $s$ 。一次操作可按如下方式进行：
$\hspace{23pt}\bullet\,$ 从 $s$ 中选择既不是最左端字符也不为 $\texttt{0}$ 的某一字符；
$\hspace{23pt}\bullet\,$ 将该字符的数值减少 $1$ ；
$\hspace{23pt}\bullet\,$ 随后把它与左侧相邻字符交换位置。

$\hspace{15pt}$ 例如，字符串 $\texttt{$ 经过一次操作可以变成 $\texttt{$ 或 $\texttt{$ 。

$\hspace{15pt}$ 你可以不限次数地执行上述操作。请计算能够得到的字典序最大的字符串，并输出该字符串。

输入描述:

第一行输入一个整数 ，表示测试用例数量。
此后  行，每行输入一个不含前导零的数字字符串 ，满足 。
保证所有测试用例的  之和不超过 。

输出描述:

对于每个测试用例，在一行上输出通过任意次数操作后能够得到的字典序最大的字符串。

示例1

输入

输出

说明

以  为例：
   ；
   ，得到答案 。

再以  为例，可按如下序列操作：
   ；
   ；
   ，最终得到答案 。

算法知识视频讲解

Python3

牛客341639822号

n = int(input()) for _ in range(n):
    st = list(map(int, input())) while True: for i in range(1, len(st)): if st[i] - st[i - 1] >= 2:
                tmp = st[i]
                st[i] = st[i - 1]
                st[i - 1] = tmp - 1  if all(st[i] -st[i-1]<2 for i in range(1, len(st))): break  print(''.join(map(str, st)))