题解 | 交换到最大

import sys
n=int(input())
ss=sys.stdin.read().splitlines()
for s in ss:
    s=list(s)#将字符串转换成列表，便于修改
    len_s=len(s)
    res=""
    for i in range(len_s):
        #设最佳值与其位置为i(寻找第i个位置的最佳元素)
        best_val=int(s[i])
        best_pos=i
        for j in range(i,min(i+10,len_s)):
        #防止越界，设置滑动窗口，位置间隔超过10，移动过来变为负数，不是最优解
            cur_val=int(s[j])-(j-i)#移动到i位置需要消耗j-i
            if cur_val>best_val:
                best_val=cur_val
                best_pos=j
        #对s进行改变
        temp_pos=best_pos
        #pop会超时，还是手动写
        while temp_pos>i:
            s[temp_pos],s[temp_pos-1]=s[temp_pos-1],s[temp_pos]
            temp_pos-=1

        s[i]=str(best_val)
    print(''.join(s))