题解 | 交换到最大

#include <iostream>
using namespace std;
int max_alter(string &s,int a,int &max){               //对字符串使用引用符号，降低时间复杂度
    max=s[a]-'0';
    int k=-1,c,n=s.size();
    for(int i=a+1;i<min(n,a+9);i++){                  //对此位置后9位的字符不予考虑
        c=s[i]-'0'-i+a;
        if(c>max){
            k=i;
            max=c;
        }
    }
    return k;
}

int main(){
    int t,k,max;
    string s;
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>s;
        for(int j=0;j<s.size()-1;j++){
            k=max_alter(s,j,max);
            if(k!=-1){
                for(int m=k;m>j;m--) s[m]=s[m-1];
                s[j]=max+'0';
            }
        }
        cout<<s<<endl;
    }
    return 0;
}