题解 | 交换到最大

// 逻辑严谨
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    string s;
    cin >> s;
    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 < min(i + 10, n); ++j) {
            int current_val = (s[j] - '0') - (j - i);
            if (current_val > best_val) {
                best_val = current_val;
                best_pos = j;
            }
        }

        // 物理移动来源字符到当前位置i
        while (best_pos > i) {
            swap(s[best_pos], s[best_pos - 1]);
            best_pos--;
        }

        // 将当前位置i的字符值更新为计算出的最优值
        s[i] = (char)(best_val + '0');
    }
    cout << s << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}