题解 | 交换到最大

贪心

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t=in.nextInt();
        while(t-->0){
            String str=in.next();
            char[] s=str.toCharArray();
            int n=s.length;
            for(int i=0;i<n;i++){
                int best_val=s[i]-'0';
                int best_pos=i;
                for(int j=i;j<Math.min(i+10,n);j++){
                    int current_val=(s[j]-'0')-(j-i);
                    if(current_val>best_val){
                        best_pos=j;
                        best_val=current_val;
                    }
                }
                int temp_pos=best_pos;
                while(temp_pos>i){
                    char temp=s[temp_pos];
                    s[temp_pos]=s[temp_pos-1];
                    s[temp_pos-1]=temp;
                    temp_pos--;
                }
                s[i]=(char)(best_val+'0');
            }
            System.out.println(new String(s));

        }
    }
}